{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T04:14:45Z","timestamp":1747973685014,"version":"3.41.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319171418"},{"type":"electronic","value":"9783319171425"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-17142-5_22","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T11:19:29Z","timestamp":1429096769000},"page":"248-259","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Finding Connected Dense $$k$$-Subgraphs"],"prefix":"10.1007","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Changjun","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-95995-3_3","volume-title":"Algorithms and Models for the Web-Graph","author":"R Andersen","year":"2009","unstructured":"Andersen, R., Chellapilla, K.: Finding dense subgraphs with size bounds. In: Avrachenkov, K., Donato, D., Litvak, N. (eds.) WAW 2009. LNCS, vol. 5427, pp. 25\u201337. Springer, Heidelberg (2009)"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 284\u2013293 (1995)","DOI":"10.1145\/225058.225140"},{"issue":"2","key":"22_CR3","doi-asserted-by":"publisher","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.: Greedily finding a dense subgraph. J. Algorithms 34(2), 203\u2013221 (2000)","journal-title":"J. Algorithms"},{"key":"22_CR4","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: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-18318-8_8","volume-title":"Approximation and Online Algorithms","author":"Danny Z Chen","year":"2011","unstructured":"Chen, Danny Z., Fleischer, Rudolf, Li, Jian: Densest k-subgraph approximation on intersection graphs. In: Jansen, Klaus, Solis-Oba, Roberto (eds.) WAOA 2010. LNCS, vol. 6534, pp. 83\u201393. Springer, Heidelberg (2011)"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Hu, X., Wang, C.: Finding connected dense $$k$$-subgraphs. CoRR abs\/1501.07348 (2015)","DOI":"10.1007\/978-3-319-17142-5_22"},{"issue":"1","key":"22_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1), 27\u201339 (1984)","journal-title":"Discrete Appl. Math."},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 637\u2013646 (2005)","DOI":"10.1109\/SFCS.2005.14"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"issue":"2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"22_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 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"22_CR12","volume-title":"Finding a Maximum Density Subgraph","author":"AV Goldberg","year":"1984","unstructured":"Goldberg, A.V.: Finding a Maximum Density Subgraph. University of California Berkeley, CA (1984)"},{"issue":"3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q Han","year":"2002","unstructured":"Han, Q., Ye, Y., Zhang, J.: An improved rounding method and semidefinite programming relaxation for graph partition. Math. Program. 92(3), 509\u2013535 (2002)","journal-title":"Math. Program."},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","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.: Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21(3), 133\u2013137 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"22_CR15","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out ptas for graph min-bisection, dense $$k$$-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"22_CR16","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. 5555, pp. 597\u2013608. Springer, Heidelberg (2009)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 692\u2013701 (1993)","DOI":"10.1109\/SFCS.1993.366818"},{"key":"22_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Courier Dover Publications, New York (1976)"},{"key":"22_CR19","unstructured":"Liazi, M., Milis, I., Zissimopoulos, V.: Polynomial variants of the densest\/heaviest $$k$$-subgraph problem. In: Proceedings of the 20th British Combinatorial Conference, Durham (2005)"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BFb0053974","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"A Srivastav","year":"1998","unstructured":"Srivastav, A., Wolf, K.: Finding dense subgraphs with semidefinite programming. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 181\u2013191. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-17142-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T15:34:35Z","timestamp":1747928075000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-17142-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319171418","9783319171425"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-17142-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}