Finding induced subgraphs in scale-free inhomogeneous random graphs

Ellen Cardinaels, Johan S. H. van Leeuwaarden, Clara Stegehuis*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Downloads (Pure)

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 languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
EditorsAnthony Bonato, Pawel Pralat, Andrei Raigorodskii
PublisherSpringer
Pages1-15
Number of pages14
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
DOIs
Publication statusPublished - 30 May 2018
Externally publishedYes
EventInternational Workshop on Algorithms and Models for the Web-Graph 2018 - Moscow, Russian Federation
Duration: 17 May 201818 May 2018

Workshop

WorkshopInternational Workshop on Algorithms and Models for the Web-Graph 2018
Abbreviated titleWAW 2018
CountryRussian Federation
CityMoscow
Period17/05/1818/05/18

Keywords

  • cs.DS
  • math.CO

Fingerprint Dive into the research topics of 'Finding induced subgraphs in scale-free inhomogeneous random graphs'. Together they form a unique fingerprint.

Cite this