Faster algorithms for counting subgraphs in sparse graphs
From MaRDI portal
Publication:2041986
Recommendations
Cites work
- A note on the graph isomorphism counting problem
- Arboricity and bipartite subgraph listing algorithms
- Arboricity and Subgraph Listing Algorithms
- Are there any good digraph width measures?
- Characterisations of nowhere dense graphs (invited talk)
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Counting graph homomorphisms
- Exact exponential algorithms.
- Faster Subgraph Counting in Sparse Graphs
- Graph theory
- Graph-Theoretic Concepts in Computer Science
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- Improved bounds on Bell numbers and on moments of sums of random variables
- Listing all maximal cliques in large sparse real-world graphs
- Listing all maximal cliques in sparse graphs in near-optimal time
- On nowhere dense graphs
- On tree width, bramble size, and expansion
- Powers of tensors and fast matrix multiplication
- Sparsity. Graphs, structures, and algorithms
- Strong computational lower bounds via parameterized complexity
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Tight lower bounds for certain parameterized NP-hard problems
- Which problems have strongly exponential complexity?
Cited in
(20)- Finding even subgraphs even faster
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- A dynamic data structure for counting subgraphs in sparse graphs
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Homomorphisms are a good basis for counting small subgraphs
- Counting connected subgraphs with maximum-degree-aware sieving
- Engineering a delegatable and error-tolerant algorithm for counting small subgraphs
- Faster Subgraph Counting in Sparse Graphs
- Counting Subgraphs in Degenerate Graphs
- Approximately counting embeddings into random graphs
- Approximately Counting Embeddings into Random Graphs
- Rare siblings speed-up deterministic detection and counting of small pattern graphs
- Counting Homomorphic Cycles in Degenerate Graphs
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- Parallel Five-cycle Counting Algorithms
- Parameterised and fine-grained subgraph counting, modulo 2
- The complexity of pattern counting in directed graphs, parameterised by the outdegree
- Turbocharging heuristics for weak coloring numbers
- A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs
- Cycle counting under local differential privacy for degeneracy-bounded graphs
This page was built for publication: Faster algorithms for counting subgraphs in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2041986)
