Abstract
We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n k)$ time for small values of $k$. We test our algorithm on several real-world data sets.
Original language | English |
---|---|
Title of host publication | Algorithms and Models for the Web Graph |
Subtitle of host publication | 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings |
Editors | Anthony Bonato, Pawel Pralat, Andrei Raigorodskii |
Publisher | Springer |
Pages | 1-15 |
Number of pages | 14 |
ISBN (Electronic) | 978-3-319-92871-5 |
ISBN (Print) | 978-3-319-92870-8 |
DOIs | |
Publication status | Published - 30 May 2018 |
Externally published | Yes |
Event | International Workshop on Algorithms and Models for the Web-Graph 2018 - Moscow, Russian Federation Duration: 17 May 2018 → 18 May 2018 |
Workshop
Workshop | International Workshop on Algorithms and Models for the Web-Graph 2018 |
---|---|
Abbreviated title | WAW 2018 |
Country/Territory | Russian Federation |
City | Moscow |
Period | 17/05/18 → 18/05/18 |
Keywords
- cs.DS
- math.CO