{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:44:18Z","timestamp":1771703058209,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642332920","type":"print"},{"value":"9783642332937","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_23","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T06:50:58Z","timestamp":1346223058000},"page":"242-251","source":"Crossref","is-referenced-by-count":14,"title":["Finding Dense Subgraphs of Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Christian","family":"Komusiewicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"23_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-540-79723-4_4","volume-title":"Parameterized and Exact Computation","author":"O. Amini","year":"2008","unstructured":"Amini, O., Sau, I., Saurabh, S.: Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 13\u201329. Springer, Heidelberg (2008)"},{"issue":"1","key":"23_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B. Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: The maximum k-plex problem. Oper. Res.\u00a059(1), 133\u2013142 (2011)","journal-title":"Oper. Res."},{"key":"23_CR4","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proc.\u00a028th\u00a0STACS. LIPIcs, vol.\u00a09, pp. 165\u2013176. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2011)"},{"issue":"1","key":"23_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L. Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J.\u00a051(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/11847250_22","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 239\u2013250. Springer, Heidelberg (2006)"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-03367-4_25","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D., Spiro, E.S.: The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 278\u2013289. Springer, Heidelberg (2009)"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-17517-6_36","volume-title":"Algorithms and Computation","author":"D. Eppstein","year":"2010","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 403\u2013414. Springer, Heidelberg (2010)"},{"key":"23_CR10","unstructured":"Feige, U., Seltser, M.: On the densest k-subgraph problem. Technical report, The Weizmann Institute, Department of Applied Math. and Computer Science (1997)"},{"issue":"3","key":"23_CR11","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"23_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput.\u00a018(1), 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"23_CR13","doi-asserted-by":"publisher","first-page":"1547","DOI":"10.1016\/j.dam.2006.01.005","volume":"154","author":"K. Holzapfel","year":"2006","unstructured":"Holzapfel, K., Kosub, S., Maa\u00df, M.G., T\u00e4ubig, H.: The complexity of detecting fixed-density clusters. Discrete Appl. Math.\u00a0154(11), 1547\u20131562 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"23_CR14","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-02927-1_50","volume-title":"Automata, Languages and Programming","author":"S. Khuller","year":"2009","unstructured":"Khuller, S., Saha, B.: On Finding Dense Subgraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 597\u2013608. Springer, Heidelberg (2009)"},{"key":"23_CR16","unstructured":"Komusiewicz, C.: Parameterized Algorithmics for Network Analysis: Clustering & Querying. PhD thesis, Technische Universit\u00e4t Berlin, Berlin, Germany (2011)"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-31955-9_6","volume-title":"Network Analysis","author":"S. Kosub","year":"2005","unstructured":"Kosub, S.: Local Density. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol.\u00a03418, pp. 112\u2013142. Springer, Heidelberg (2005)"},{"key":"23_CR18","first-page":"41","volume":"105","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS\u00a0105, 41\u201372 (2011)","journal-title":"Bulletin of the EATCS"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-642-12683-3_30","volume-title":"Research in Computational Molecular Biology","author":"B. Saha","year":"2010","unstructured":"Saha, B., Hoch, A., Khuller, S., Raschid, L., Zhang, X.-N.: Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol.\u00a06044, pp. 456\u2013472. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:03:27Z","timestamp":1620115407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}