TY - GEN

T1 - Computing the degeneracy of large graphs

AU - Farach-Colton, Martín

AU - Tsai, Meng Tsung

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84899944191&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899944191&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-54423-1_22

DO - 10.1007/978-3-642-54423-1_22

M3 - Conference contribution

AN - SCOPUS:84899944191

SN - 9783642544224

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 250

EP - 260

BT - LATIN 2014

PB - Springer Verlag

T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -