Computing the degeneracy of large graphs

Martín Farach-Colton, Meng-Tsung Tsai

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

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
Title of host publicationLATIN 2014
Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
PublisherSpringer Verlag
Pages250-260
Number of pages11
ISBN (Print)9783642544224
DOIs
StatePublished - 1 Jan 2014
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 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

Conference

Conference11th Latin American Theoretical Informatics Symposium, LATIN 2014
CountryUruguay
CityMontevideo
Period31/03/144/04/14

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

Cite this