Counting Subgraphs in Degenerate Graphs

DOI10.1145/3520240OpenAlexW4220820401MaRDI QIDQ5889797FDOQ5889797

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

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

zbMATH Keywords

degeneracygraph algorithmslinear time algorithmssubgraph counting

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

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

Cited In (11)

• 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
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Counting subgraphs in hyperbolic graphs with symmetry
• Title not available (Why is that?)
• Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
• Parameterised and fine-grained subgraph counting, modulo 2

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)