Tight Approximations of Degeneracy in Large Graphs

DOI10.1007/978-3-662-49529-2_32zbMath1476.68204OpenAlexW2461496720MaRDI QIDQ2802958

Meng-Tsung Tsai, Martín Farach-Colton

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

thicknessdegeneracyarboricitysemi-streaming algorithmspace lower bound

Mathematics Subject Classification ID

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

Related Items (2)

Single-pass streaming algorithms to partition graphs into few forests ⋮ Optimality of linear sketching under modular updates

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