Computing the degeneracy of large graphs

Martín Farach-Colton, Meng Tsung Tsai

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


    Any ordering of the nodes of an n-node, m-edge simple undirected graph G defines an acyclic orientation of the edges in which each edge is oriented from the earlier node in the ordering to the later. The degeneracy on an ordering is the maximum outdegree it induces, and the degeneracy of a graph is smallest degeneracy of any node ordering. Small-degeneracy orderings have many applications. We give an algorithm for generating an ordering whose degeneracy approximates the minimum possible, that is, it approximates the degeneracy of the graph. Although the optimal ordering itself can be computed in O(m)time and O(m) space, such algorithms are infeasible for large graphs. Our approximation algorithm is semi-streaming: it uses less space, can achieve a constant approximation ratio, and accesses the graph in logarithmic read-only passes.

    Original languageEnglish (US)
    Title of host publicationLATIN 2014
    Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
    PublisherSpringer Verlag
    Number of pages11
    ISBN (Print)9783642544224
    StatePublished - 2014
    Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
    Duration: Mar 31 2014Apr 4 2014

    Publication series

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


    Conference11th Latin American Theoretical Informatics Symposium, LATIN 2014

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


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

    Cite this