Faster algorithms for counting subgraphs in sparse graphs

DOI10.1007/s00453-021-00811-0OpenAlexW3132242427MaRDI QIDQ2041986

Marco Bressan

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.02089

zbMATH Keywords

tree decompositiondegeneracysparsitysubgraph counting

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (4)

Counting Subgraphs in Degenerate Graphs ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Exact exponential algorithms.
• Strong computational lower bounds via parameterized complexity
• Are there any good digraph width measures?
• A note on the graph isomorphism counting problem
• Arboricity and bipartite subgraph listing algorithms
• Which problems have strongly exponential complexity?
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• On nowhere dense graphs
• On tree width, bramble size, and expansion
• Tight lower bounds for certain parameterized NP-hard problems
• Graph Theory
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Powers of tensors and fast matrix multiplication
• Arboricity and Subgraph Listing Algorithms
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Homomorphisms are a good basis for counting small subgraphs
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Faster Subgraph Counting in Sparse Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Faster algorithms for counting subgraphs in sparse graphs