Tight approximations of degeneracy in large graphs

Martín Farach-Colto, Meng Tsung Tsai

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationLATIN 2016
    Subtitle of host publicationTheoretical Informatics - 12th Latin American Symposium, Proceedings
    EditorsGonzalo Navarro, Evangelos Kranakis, Edgar Chávez
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)9783662495285
    StatePublished - 2016
    Event12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico
    Duration: Apr 11 2016Apr 15 2016

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference12th Latin American Symposium on Theoretical Informatics, LATIN 2016


    • Arboricity
    • Degeneracy
    • Semi-streaming algorithm
    • Space lower bound
    • Thickness

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Tight approximations of degeneracy in large graphs'. Together they form a unique fingerprint.

    Cite this