Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUBGRAPH:
Reports tagged with subgraph:
TR20-177 | 12th October 2020
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Counting Subgraphs in Degenerate Graphs

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

ISSN 1433-8092 | Imprint