{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:19:23Z","timestamp":1725851963006},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_32","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T04:09:41Z","timestamp":1458533381000},"page":"429-440","source":"Crossref","is-referenced-by-count":5,"title":["Tight Approximations of Degeneracy in Large Graphs"],"prefix":"10.1007","author":[{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"first","affiliation":[]},{"given":"Meng-Tsung","family":"Tsai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"32_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/978-3-642-22012-8_42","volume-title":"Automata, Languages and Programming","author":"KJ Ahn","year":"2011","unstructured":"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\u2013538. Springer, Heidelberg (2011)"},{"issue":"3","key":"32_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"32_CR3","unstructured":"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), pp. 623\u2013632. SIAM (2002)"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D., Tsourakakis, C.E.: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pp. 173\u2013182 (2015)","DOI":"10.1145\/2746539.2746592"},{"key":"32_CR5","volume-title":"Extremal Graph Theory","author":"B Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, London (1978)"},{"key":"32_CR6","unstructured":"Bollob\u00e1s, B.: The evolution of sparse graphs. In: Graph Theory and Combinatorics, Proceedings of the Cambridge Combinatorial Conference in honor of Paul Erd\u0151s, pp. 35\u201357. Academic Press (1984)"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M Charikar","year":"2000","unstructured":"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\u201395. Springer, Heidelberg (2000)"},{"key":"32_CR8","unstructured":"Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to dynamic graph streams, CoRR abs\/1505.01731 (2015)"},{"issue":"1","key":"32_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0095-8956(91)90100-X","volume":"52","author":"AM Dean","year":"1991","unstructured":"Dean, A.M., Hutchinson, J.P., Scheinerman, E.R.: On the thickness and arboricity of a graph. J. Comb. Theor. Series B 52(1), 147\u2013151 (1991)","journal-title":"J. Comb. Theor. Series B"},{"issue":"5","key":"32_CR10","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Z Dvor\u0306\u00e1k","year":"2013","unstructured":"Dvor\u0306\u00e1k, Z.: Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb. 34(5), 833\u2013840 (2013)","journal-title":"Eur. J. Comb."},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-319-21840-3_30","volume-title":"Algorithms and Data Structures","author":"M Farach-Colton","year":"2015","unstructured":"Farach-Colton, M., Hsu, T., Li, M., Tsai, M.-T.: Finding articulation points of large graphs in linear time. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 363\u2013372. Springer, Heidelberg (2015)"},{"key":"32_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-54423-1_22","volume-title":"LATIN 2014: Theoretical Informatics","author":"M Farach-Colton","year":"2014","unstructured":"Farach-Colton, M., Tsai, M.-T.: Computing the degeneracy of large graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 250\u2013260. Springer, Heidelberg (2014)"},{"issue":"2","key":"32_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR14","unstructured":"Frank, A., Gyarfas, A.: How to orient the edges of a graph. In: Proceedings of the Fifth Hungarian Colloquium on Combinatorics. vol. I, Combinatorics, pp. 353\u2013364 (1976)"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"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), pp. 407\u2013421. ACM (1988)","DOI":"10.1145\/62212.62252"},{"key":"32_CR16","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report (1984)"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems (PODS), pp. 241\u2013247 (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. In: 28th Conference on Computational Complexity (CCC), pp. 287\u2013298. IEEE (2013)","DOI":"10.1109\/CCC.2013.37"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Sa\u011flam, M., Tardos, G.: Tight bounds for \n                    \n                      \n                    \n                    $${L}_p$$\n                    \n                      \n                        \n                          L\n                          p\n                        \n                      \n                    \n                   samplers, finding duplicates in streams, and related problems. In: Proceedings of the 30th ACM Symposium on Principles of Database Systems (PODS), pp. 49\u201358. ACM (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 561\u2013570 (2014)","DOI":"10.1109\/FOCS.2014.66"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.P.: Spanners and sparsifiers in dynamic streams. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 272\u2013281 (2014)","DOI":"10.1145\/2611462.2611497"},{"issue":"6","key":"32_CR22","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0020-0190(02)00432-5","volume":"85","author":"S Kawano","year":"2003","unstructured":"Kawano, S., Yamazaki, K.: Worst case analysis of a greedy algorithm for graph thickness. Inf. Process. Lett. 85(6), 333\u2013337 (2003)","journal-title":"Inf. Process. Lett."},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/978-3-662-48350-3_70","volume-title":"Algorithms - ESA 2015","author":"C Konrad","year":"2015","unstructured":"Konrad, C.: Maximum matching in turnstile streams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 840\u2013852. Springer, Verlag (2015)"},{"key":"32_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/11940128_56","volume-title":"Algorithms and Computation","author":"\u0141 Kowalik","year":"2006","unstructured":"Kowalik, \u0141.: Approximation scheme for lowest outdegree orientation and graph density measures. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 557\u2013566. Springer, Heidelberg (2006)"},{"key":"32_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-319-08404-6_27","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"K Kutzkov","year":"2014","unstructured":"Kutzkov, K., Pagh, R.: Triangle counting in dynamic graph streams. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 306\u2013318. Springer, Heidelberg (2014)"},{"key":"32_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-15763-9_48","volume-title":"Distributed Computing","author":"C Lenzen","year":"2010","unstructured":"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\u2013524. Springer, Heidelberg (2010)"},{"key":"32_CR27","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1017\/S030500410006028X","volume":"93","author":"A Mansfield","year":"1983","unstructured":"Mansfield, A.: Determining the thickness of graphs is NP-hard. Math. Proc. Cambridge Philos. Soc. 93, 9\u201323 (1983)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"3","key":"32_CR28","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"32_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/978-3-662-48054-0_39","volume-title":"Mathematical Foundations of Computer Science 2015","author":"A McGregor","year":"2015","unstructured":"McGregor, A., Tench, D., Vorotnikova, S., Vu, H.T.: Densest subgraph in dynamic graph streams. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 472\u2013482. Springer, Heidelberg (2015)"},{"key":"32_CR30","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Technical report (2003)"},{"issue":"1","key":"32_CR31","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"s1\u201336","author":"CSA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. s1\u201336(1), 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"32_CR32","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-1-4020-9688-4_17","volume-title":"Fundamental Problems in Computing","author":"TC O\u2019Connell","year":"2009","unstructured":"O\u2019Connell, T.C.: A survey of graph algorithms under extended streaming models of computation. In: Ravi, S.S., Shukla, S.K. (eds.) Fundamental Problems in Computing, pp. 455\u2013476. Springer, The Netherlands (2009)"},{"key":"32_CR33","unstructured":"Ruhl, J.M.: Efficient algorithms for new computational models. Ph.D. thesis, Massachusetts Institute of Technology, September 2003"},{"key":"32_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/11427186_54","volume-title":"Experimental and Efficient Algorithms","author":"T Schank","year":"2005","unstructured":"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\u2013609. Springer, Heidelberg (2005)"},{"key":"32_CR35","unstructured":"Sun, X., Woodruff, D.P.: Tight bounds for graph problems in insertion streams. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM, pp. 435\u2013448 (2015)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T23:27:58Z","timestamp":1548026878000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}