Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
| Authors | |
|---|---|
| Publication date | 05-2019 |
| Journal | Algorithmica |
| Volume | Issue number | 81 | 5 |
| Pages (from-to) | 1844–1858 |
| Organisations |
|
| Abstract | In this paper we show that for any graph H of order m and any graph G of order n and maximum degree Δ one can compute the number of subsets S of V(G) that induces a graph isomorphic to H in time O(cm⋅n) for some constant c=c(Δ)>0 . This is essentially best possible (in the sense that there is noco(m)poly(n) -time algorithm under the exponential time hypothesis). |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1007/s00453-018-0511-9 |
| Other links | https://www.scopus.com/pages/publications/85053416858 |
| Downloads |
Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
(Final published version)
|
| Permalink to this page | |