{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T21:20:58Z","timestamp":1775942458163,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642360640","type":"print"},{"value":"9783642360657","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36065-7_12","type":"book-chapter","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T16:36:53Z","timestamp":1358786213000},"page":"114-125","source":"Crossref","is-referenced-by-count":14,"title":["Exact and Approximation Algorithms for Densest k-Subgraph"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Bourgeois","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aristotelis","family":"Giannakos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Lucarelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Milis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","volume":"121","author":"Y. Asahiro","year":"2002","unstructured":"Asahiro, Y., Hassin, R., Iwama, K.: Complexity of finding dense subgraphs. Discrete Applied Mathematics\u00a0121, 15\u201326 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: An O(n 1\/4) approximation for densest k-subgraph. In: STOC 2010, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1504\/IJOR.2008.017534","volume":"3","author":"A. Billionnet","year":"2008","unstructured":"Billionnet, A., Roupin, F.: A deterministic approximation algorithm for the densest k-subgraph problem. International Journal of Operational Research\u00a03, 301\u2013314 (2008)","journal-title":"International Journal of Operational Research"},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM Journal of Computing\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM Journal of Computing"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"17","key":"12_CR7","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N. Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Applied Mathematics\u00a0159(17), 1954\u20131970 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N. Bourgeois","year":"2012","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica\u00a062, 382\u2013415 (2012)","journal-title":"Algorithmica"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s10878-010-9343-5","volume":"23","author":"N. Bourgeois","year":"2012","unstructured":"Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V.T., Potti\u00e9, O.: The max quasi-independent set problem. Journal of Combinatorial Optimization\u00a023, 94\u2013117 (2012)","journal-title":"Journal of Combinatorial Optimization"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V.T.: The Exact and approximation algorithms for densest k -subgraph. Cahiers du LAMSADE (324) (2012)","DOI":"10.1007\/978-3-642-36065-7_12"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-642-17517-6_35","volume-title":"Algorithms and Computation","author":"L. Brankovic","year":"2010","unstructured":"Brankovic, L., Fernau, H.: Combining Two Worlds: Parameterised Approximation for Vertex Cover. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 390\u2013402. Springer, Heidelberg (2010)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L. Cai","year":"2007","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. The Computer Journal\u00a051, 102\u2013121 (2007)","journal-title":"The Computer Journal"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11847250_9","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Huang, X.: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 96\u2013108. Springer, Heidelberg (2006)"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science\u00a0411, 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"16","key":"12_CR15","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M. Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Information Processing Letters\u00a0109(16), 957\u2013961 (2009)","journal-title":"Information Processing Letters"},{"issue":"40-42","key":"12_CR16","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theoretical Computer Science\u00a0411(40-42), 3701\u20133713 (2010)","journal-title":"Theoretical Computer Science"},{"key":"12_CR17","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R.G. Downey","year":"2006","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized Approximation Problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029, 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM\u00a056 (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"12_CR21","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: FOCS 2004, pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"key":"12_CR25","unstructured":"Moser, H.: Exact algorithms for generalizations of vertex cover. PhD thesis, Friedrich-Schiller-Universit\u00e4t Jena (2005)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36065-7_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T17:54:12Z","timestamp":1745949252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36065-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360640","9783642360657"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36065-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}