Bounded Arboricity to Determine the Local Structure of Sparse Graphs

DOI10.1007/11917496_15MaRDI QIDQ3522953zbMATH OpenOpenAlexFDO

Authors Gaurav Goel, Jens Gustedt

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_15

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Computing Communities in Large Networks Using Random Walks
• Local structure theorems for Erdős-Rényi graphs and their algorithmic applications
• Community detection in sparse random networks

Cited in

(8)

• A new decomposition technique for maximal clique enumeration for sparse graphs
• Maximal strongly connected cliques in directed graphs: algorithms and bounds
• Fully dynamic MIS in uniformly sparse graphs
• The arboricity captures the complexity of sampling edges
• Local structure theorems for Erdős-Rényi graphs and their algorithmic applications
• On maximal cliques with connectivity constraints in directed graphs
• Near-optimal distributed dominating set in bounded arboricity graphs
• A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs

This page was built for publication: Bounded Arboricity to Determine the Local Structure of Sparse Graphs

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