Tight Approximations of Degeneracy in Large Graphs

DOI10.1007/978-3-662-49529-2_32MaRDI QIDQ2802958zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Meng-Tsung Tsai

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-49529-2_32

zbMATH Keywords

arboricitydegeneracysemi-streaming algorithmspace lower boundthickness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Computing the degeneracy of large graphs
• Tight kernel bounds for problems on graphs with small degeneracy
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Approximation and decomposition by extremal graphs
• Degeneracy graphs: Theory and applications. An updated survey
• Degeneracy graphs and the neighbourhood problem
• Efficient algorithms for decomposing graphs under degree constraints
• scientific article; zbMATH DE number 89070
• A theory of degeneracy graphs
• Tight bounds for finding degrees from the adjacency matrix

Cited in

(6)

• Single-pass streaming algorithms to partition graphs into few forests
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Optimality of linear sketching under modular updates
• Computing the degeneracy of large graphs
• Graph coloring via degeneracy in streaming and other space-conscious models
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy

This page was built for publication: Tight Approximations of Degeneracy in Large Graphs

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