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 \(\mathcal{O}(m)\) time and \(\mathcal{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.
Work supported by NSF Grants IIS-1247750 and CCF-1114930
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 526–538. Springer, Heidelberg (2011)
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997)
Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 623–632. Society for Industrial and Applied Mathematics (2002)
Bollobás, B.: Extremal graph theory. Academic Press (1978)
Bollobás, B.: The evolution of sparse graphs. In: Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf., pp. 35–57. Academic Press (1984)
Chakrabarti, A., Cormode, G., McGregor, A.: Annotations in data streams. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 222–234. Springer, Heidelberg (2009)
Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 84–95. Springer, Heidelberg (2000)
Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 693–703. Springer, Heidelberg (2002)
Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. Proc. VLDB Endow. 1(2), 1530–1541 (2008)
Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58–75 (2005)
Dean, A.M., Hutchinson, J.P., Scheinerman, E.R.: On the thickness and arboricity of a graph. Journal of Combinatorial Theory, Series B 52(1), 147–151 (1991)
Dvořák, Z.: Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics 34(5), 833–840 (2013)
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 531–543. Springer, Heidelberg (2004)
Frank, A., Gyarfas, A.: How to orient the edges of a graph. In: Combinatorics Volume I, Proc. of the Fifth Hungarian Colloquium on Combinatorics, vol. I, pp. 353–364 (1976)
Gabow, H., Westermann, H.: Forests, frames, and games: algorithms for matroid sums and applications. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988 pp. 407–421. ACM (1988)
Goldberg, A.V.: Finding a maximum density subgraph. Tech. rep. (1984)
Kawano, S., Yamazaki, K.: Worst case analysis of a greedy algorithm for graph thickness. Information Processing Letters 85(6), 333–337 (2003)
Kowalik, Ł.: Approximation scheme for lowest outdegree orientation and graph density measures. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 557–566. Springer, Heidelberg (2006)
Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 510–524. Springer, Heidelberg (2010)
Liu, P., Wang, D.W., Wu, J.J.: Efficient parallel i/o scheduling in the presence of data duplication. In: International Conference on Parallel Processing, pp. 231–238 (2003)
Mansfield, A.: Determining the thickness of graphs is NP-hard. Math. Proc. Cambridge Philos. Soc. 93, 9–23 (1983)
Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)
Muthukrishnan, S.: Data streams: Algorithms and applications. Tech. rep. (2003)
O’Connell, T.C.: A survey of graph algorithms under extended streaming models of computation. In: Fundamental Problems in Computing, pp. 455–476. Springer, Netherlands (2009)
Ruhl, J.M.: Efficient Algorithms for New Computational Models. Ph.D. thesis, Massachusetts Institute of Technology (September 2003)
Schank, T., Wagner, D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 606–609. Springer, Heidelberg (2005)
Zhang, J.: A survey on streaming algorithms for massive graphs. In: Managing and Mining Graph Data, Advances in Database Systems, vol. 40, pp. 393–420. Springer, US (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farach-Colton, M., Tsai, MT. (2014). Computing the Degeneracy of Large Graphs. In: Pardo, A., Viola, A. (eds) LATIN 2014: Theoretical Informatics. LATIN 2014. Lecture Notes in Computer Science, vol 8392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-54423-1_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54422-4
Online ISBN: 978-3-642-54423-1
eBook Packages: Computer ScienceComputer Science (R0)