6 citations · 7 across the 5 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022★ 1 cited
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
cs.CC2021
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
Marco Bressan, Marc Roth
We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a -vertex graph in a -degenerate -vertex graph . Our ma…
cs.CC2018
Faster algorithms for counting subgraphs in sparse graphs
Marco Bressan
Given a -node pattern graph and an -node host graph , the subgraph counting problem asks to compute the number of copies of in . In this work we address the fol…