Finding induced subgraphs in scale-free inhomogeneous random graphs

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
TitelAlgorithms and Models for the Web Graph
Subtitel15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
RedacteurenA. Bonato, P. Pralat, A. Raigorodskii
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's1-15
Aantal pagina's15
ISBN van elektronische versie978-3-319-92871-5
ISBN van geprinte versie978-3-319-92870-8
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Rusland
Duur: 17 mei 201818 mei 2018

Publicatie series

NaamLecture Notes in Computer Science
Volume10836
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres15th Workshop on Algorithms and Models for the Web Graph, WAW 2018
LandRusland
StadMoscow
Periode17/05/1818/05/18

Vingerafdruk Duik in de onderzoeksthema's van 'Finding induced subgraphs in scale-free inhomogeneous random graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit