Faster algorithms for counting subgraphs in sparse graphs
From MaRDI portal
Publication:2041986
DOI10.1007/s00453-021-00811-0OpenAlexW3132242427MaRDI QIDQ2041986
Publication date: 26 July 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.02089
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
