Faster Subgraph Counting in Sparse Graphs

DOI10.4230/LIPICS.IPEC.2019.6MaRDI QIDQ5875538zbMATH OpenOpenAlexFDO

Authors Marco Bressan

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.IPEC.2019.6

zbMATH Keywords

degeneracysubgraph countingtree decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Faster algorithms for counting subgraphs in sparse graphs
• Faster algorithms for finding and counting subgraphs
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Counting and detecting small subgraphs via equations
• Homomorphisms are a good basis for counting small subgraphs

Cited in

(12)

• Finding even subgraphs even faster
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Faster algorithms for counting subgraphs in sparse graphs
• Finding and counting small induced subgraphs efficiently
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Counting connected subgraphs with maximum-degree-aware sieving
• Counting Subgraphs in Degenerate Graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Finding and counting small tournaments in large tournaments
• A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs

This page was built for publication: Faster Subgraph Counting in Sparse Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875538)