@inproceedings{4796ce3026624ea4b0498f49c7c8445f,

title = "Tight approximations of degeneracy in large graphs",

abstract = "Given an n-node m-edge graph G, the degeneracy of graph G and the associated node ordering can be computed in linear time in the RAM model by a greedy algorithm that iteratively removes the node of min-degree [28]. In the semi-streaming model for large graphs, where memory is limited to O(n polylog n) and edges can only be accessed in sequential passes, the greedy algorithm requires too many passes, so another approach is needed. In the semi-streaming model, there is a deterministic log-pass algorithm for generating an ordering whose degeneracy approximates the minimum possible to within a factor of (2+ε) for any constant ε > 0 [12]. In this paper, we propose a randomized algorithm that improves the approximation factor to (1 + ε) with high probability and needs only a single pass. Our algorithm can be generalized to the model that allows edge deletions, but then it requires more computation and space usage. The generated node ordering not only yields a (1+ε)-approximation for the degeneracy but gives constant-factor approximations for arboricity and thickness.",

keywords = "Arboricity, Degeneracy, Semi-streaming algorithm, Space lower bound, Thickness",

author = "Mart{\'i}n Farach-Colto and Tsai, {Meng Tsung}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 ; Conference date: 11-04-2016 Through 15-04-2016",

year = "2016",

doi = "10.1007/978-3-662-49529-2_32",

language = "English (US)",

isbn = "9783662495285",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "429--440",

editor = "Gonzalo Navarro and Evangelos Kranakis and Edgar Ch{\'a}vez",

booktitle = "LATIN 2016",

}