Counting Subgraphs in Degenerate Graphs

DOI10.1145/3520240MaRDI QIDQ5889797zbMATH OpenOpenAlexFDO

Authors Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira

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

zbMATH Keywords

degeneracygraph algorithmslinear time algorithmssubgraph counting

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Faster Subgraph Counting in Sparse Graphs
• Faster algorithms for counting subgraphs in sparse graphs
• Homomorphisms are a good basis for counting small subgraphs
• Approximately counting embeddings into random graphs
• Study on the counting of subgraphs in degenerate graph

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• scientific article; zbMATH DE number 2110413 (Why is no real title available?)
• scientific article; zbMATH DE number 7650386 (Why is no real title available?)
• A course in combinatorics.
• Arboricity and Subgraph Listing Algorithms
• Color-coding
• Counting Paths and Packings in Halves
• Counting and detecting small subgraphs via equations
• Efficient algorithms for clique problems
• Emergence of Scaling in Random Networks
• Faster algorithms for counting subgraphs in sparse graphs
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Finding and counting small induced subgraphs efficiently
• Finding, minimizing, and counting weighted subgraphs
• Generalized quasirandom graphs
• Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
• Homomorphisms are a good basis for counting small subgraphs
• Large networks and graph limits
• Multiplying matrices faster than coppersmith-winograd
• On the Desirability of Acyclic Database Schemes
• On the complexity of fixed parameter clique and dominating set
• Quasi-random graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Sparsity. Graphs, structures, and algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Parameterized Complexity of Counting Problems
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of counting homomorphisms seen from the other side

Cited in

(11)

• Parameterised and fine-grained subgraph counting, modulo 2
• Supersaturation for subgraph counts
• Counting Subgraphs via Homomorphisms
• Counting Homomorphic Cycles in Degenerate Graphs
• Counting subgraphs in somewhere dense graphs
• Finding and counting small tournaments in large tournaments
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting subgraphs in hyperbolic graphs with symmetry
• scientific article; zbMATH DE number 6322906 (Why is no real title available?)
• Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule

This page was built for publication: Counting Subgraphs in Degenerate Graphs

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