{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T14:11:36Z","timestamp":1770127896311,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2007,9,27]]},"DOI":"10.1007\/s10878-007-9069-1","type":"journal-article","created":{"date-parts":[[2007,3,20]],"date-time":"2007-03-20T15:52:00Z","timestamp":1174405920000},"page":"465-474","source":"Crossref","is-referenced-by-count":15,"title":["The densest k-subgraph problem on clique graphs"],"prefix":"10.1007","volume":"14","author":[{"given":"Maria","family":"Liazi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Milis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fanny","family":"Pascual","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vassilis","family":"Zissimopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"9069_CR1","doi-asserted-by":"crossref","unstructured":"Arora S, Karger D, Karpinski M (1995) Polynomial time approximation schemes for dense instances of NP-hard problems. In: Proceedings of the 27th annual ACM symposium on theory of computing, pp\u00a0284\u2013293","DOI":"10.1145\/225058.225140"},{"issue":"2","key":"9069_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y Asahiro","year":"2000","unstructured":"Asahiro Y, Iwama K, Tamaki H, Tokuyama T (2000) Greedily finding a dense subgraph. J Algorithms 34(2):203\u2013221","journal-title":"J Algorithms"},{"key":"9069_CR3","unstructured":"Billionnet A, Roupin F (2004) A deterministic algorithm for the densest k-subgraph problem using linear programming. Technical Report No.\u00a0486, CEDRIC, CNAM-IIE, Paris"},{"key":"9069_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil DG, Perl Y (1984) Clustering and domination in perfect graphs. Discret Appl Math 9:27\u201339","journal-title":"Discret Appl Math"},{"issue":"3","key":"9069_CR5","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige U, Kortsarz G, Peleg D (2001) The dense k-subgraph problem. Algorithmica 29(3):410\u2013421","journal-title":"Algorithmica"},{"issue":"2","key":"9069_CR6","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige U, Langberg M (2001) Approximation algorithms for maximization problems arising in graph partitioning. J Algorithms 41(2):174\u2013211","journal-title":"J Algorithms"},{"key":"9069_CR7","unstructured":"Feige U, Seltser M (1997) On the densest k-subgraph problem. Technical Report CS97-16, Weizmann Institute"},{"issue":"2","key":"9069_CR8","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril F (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of chordal graph. SIAM J Comput 1(2):180\u2013187","journal-title":"SIAM J Comput"},{"issue":"2","key":"9069_CR9","first-page":"159","volume":"74","author":"O Goldschmidt","year":"1997","unstructured":"Goldschmidt O, Hochbaum D (1997) k-edge subgraph problems. Discret Appl Math Comb Oper Res Comput Sci 74(2):159\u2013169","journal-title":"Discret Appl Math Comb Oper Res Comput Sci"},{"issue":"3","key":"9069_CR10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q Han","year":"2002","unstructured":"Han Q, Ye Y, Zhang J (2002) An improved rounding method and semidefinite programming relaxation for graph partition. Math Program 92(3):509\u2013535","journal-title":"Math Program"},{"issue":"3","key":"9069_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0167-6377(97)00034-5","volume":"21","author":"R Hassin","year":"1997","unstructured":"Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper Res Lett 21(3):133\u2013137","journal-title":"Oper Res Lett"},{"key":"9069_CR12","first-page":"155","volume":"9","author":"JM Keil","year":"1991","unstructured":"Keil JM, Brecht TB (1991) The complexity of clustering in planar graphs. J Comb Math Comb Comput 9:155\u2013159","journal-title":"J Comb Math Comb Comput"},{"key":"9069_CR13","doi-asserted-by":"crossref","unstructured":"Khot S (2004) Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, pp\u00a0136\u2013145","DOI":"10.1109\/FOCS.2004.59"},{"key":"9069_CR14","doi-asserted-by":"crossref","unstructured":"Kortsarz G, Peleg D (1993) On choosing a dense subgraph. In: Proceedings of the 34th annual IEEE symposium on foundations of computer science, pp\u00a0692\u2013701","DOI":"10.1109\/SFCS.1993.366818"},{"key":"9069_CR15","unstructured":"Maffioli F (1991) Finding a best subtree of a tree. Technical Report 91.041, Politechnico di Milano, Dipartimento di Elektronica"},{"issue":"4","key":"9069_CR16","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0604050","volume":"4","author":"Y Perl","year":"1983","unstructured":"Perl Y, Shiloach Y (1983) Efficient optimization of monotonic functions on trees. SIAM J Algebr Discret Methods 4(4):512\u2013516","journal-title":"SIAM J Algebr Discret Methods"},{"issue":"3","key":"9069_CR17","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"DJ Rader","year":"2002","unstructured":"Rader DJ, Woeginger GJ (2002) The quadratic 0\u20131 knapsack problem with series-parallel support. Oper Res Lett 30(3):159\u2013166","journal-title":"Oper Res Lett"},{"issue":"2","key":"9069_CR18","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper Res 42(2):299\u2013310","journal-title":"Oper Res"},{"key":"9069_CR19","doi-asserted-by":"crossref","unstructured":"Srivastav A, Wolf K (1998) Finding dense subgraphs with semidefinite programming. In: Proceedings of the international workshop on approximation algorithms for combinatorial optimization, pp\u00a0181\u2013191","DOI":"10.1007\/BFb0053974"},{"key":"9069_CR20","unstructured":"Ye Y, Zhang J (1999) .519 approximation of dense-n\/2-subgraph. Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9069-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9069-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9069-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:11Z","timestamp":1559276291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9069-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3,21]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9,27]]}},"alternative-id":["9069"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9069-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3,21]]}}}