### 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 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 | A. Bonato, P. Pralat, A. Raigorodskii |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 1-15 |

Number of pages | 15 |

ISBN (Electronic) | 978-3-319-92871-5 |

ISBN (Print) | 978-3-319-92870-8 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Russian Federation Duration: 17 May 2018 → 18 May 2018 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 10836 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 |
---|---|

Country | Russian Federation |

City | Moscow |

Period | 17/05/18 → 18/05/18 |

### Fingerprint

### Cite this

*Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings*(pp. 1-15). (Lecture Notes in Computer Science; Vol. 10836). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-92871-5_1

}

*Algorithms and Models for the Web Graph: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings.*Lecture Notes in Computer Science, vol. 10836, Springer, Dordrecht, pp. 1-15, 15th Workshop on Algorithms and Models for the Web Graph, WAW 2018, Moscow, Russian Federation, 17/05/18. https://doi.org/10.1007/978-3-319-92871-5_1

**Finding induced subgraphs in scale-free inhomogeneous random graphs.** / Cardinaels, Ellen; van Leeuwaarden, Johan S.H.; Stegehuis, Clara.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Finding induced subgraphs in scale-free inhomogeneous random graphs

AU - Cardinaels, Ellen

AU - van Leeuwaarden, Johan S.H.

AU - Stegehuis, Clara

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85048226583&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-92871-5_1

DO - 10.1007/978-3-319-92871-5_1

M3 - Conference contribution

AN - SCOPUS:85048226583

SN - 978-3-319-92870-8

T3 - Lecture Notes in Computer Science

SP - 1

EP - 15

BT - Algorithms and Models for the Web Graph

A2 - Bonato, A.

A2 - Pralat, P.

A2 - Raigorodskii, A.

PB - Springer

CY - Dordrecht

ER -