Counting Subgraphs in Degenerate Graphs
From MaRDI portal
Publication:5889797
DOI10.1145/3520240OpenAlexW4220820401MaRDI QIDQ5889797
Lior Gishboliner, Suman K. Bera, Asaf Shapira, Yevgeny Levanzov, C. Seshadhri
Publication date: 27 April 2023
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.05998
Related Items (3)
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
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Sparsity. Graphs, structures, and algorithms
- Finding and counting given length cycles
- On the complexity of fixed parameter clique and dominating set
- The complexity of counting homomorphisms seen from the other side
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Efficient algorithms for clique problems
- Faster algorithms for counting subgraphs in sparse graphs
- Generalized quasirandom graphs
- Counting and Detecting Small Subgraphs via Equations
- On the Desirability of Acyclic Database Schemes
- Emergence of Scaling in Random Networks
- Counting Paths and Packings in Halves
- Arboricity and Subgraph Listing Algorithms
- Smallest-last ordering and clustering and graph coloring algorithms
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Finding a Minimum Circuit in a Graph
- Color-coding
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- The Parameterized Complexity of Counting Problems
- Homomorphisms are a good basis for counting small subgraphs
- Finding, minimizing, and counting weighted subgraphs
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Multiplying matrices faster than coppersmith-winograd
- Quasi-random graphs
This page was built for publication: Counting Subgraphs in Degenerate Graphs
