Finding induced subgraphs in scale-free inhomogeneous random graphs

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

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

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(nk) 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
EditorsA. Bonato, P. Pralat, A. Raigorodskii
Place of PublicationDordrecht
PublisherSpringer
Pages1-15
Number of pages15
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
DOIs
Publication statusPublished - 1 Jan 2018
Event15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Russian Federation
Duration: 17 May 201818 May 2018

Publication series

NameLecture Notes in Computer Science
Volume10836
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Workshop on Algorithms and Models for the Web Graph, WAW 2018
CountryRussian Federation
CityMoscow
Period17/05/1818/05/18

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

Cite this