{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T17:37:06Z","timestamp":1725817026718},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319156118"},{"type":"electronic","value":"9783319156125"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-15612-5_2","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T04:05:18Z","timestamp":1424664318000},"page":"8-19","source":"Crossref","is-referenced-by-count":0,"title":["Fast Algorithms for Constrained Graph Density Problems"],"prefix":"10.1007","author":[{"given":"Venkatesan","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Neelima","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Aditya","family":"Pancholi","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (1992)"},{"key":"2_CR2","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.\u00a05427, pp. 25\u201337. Springer, Heidelberg (2009)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an o(n1\/4) approximation for densest k-subgraph. In: STOC, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"2_CR4","unstructured":"Chakaravarthy, V.T., Modani, N., Natarajan, S.R., Roy, S., Sabharwal, Y.: Density functions subject to a co-matroid constraint. In: FSTTCS, pp. 236\u2013248 (2012)"},{"key":"2_CR5","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.\u00a01913, pp. 84\u201395. Springer, Heidelberg (2000)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N.: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, June 1-4, pp. 735\u2013744 (2013)","DOI":"10.1145\/2488608.2488702"},{"key":"2_CR7","first-page":"2001","volume":"29","author":"U. Feige","year":"1999","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029, 2001 (1999)","journal-title":"Algorithmica"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Gajewar, A., Sarma, A.D.: Multi-skill collaborative teams based on densest subgraphs. In: SDM, pp. 165\u2013176 (2012)","DOI":"10.1137\/1.9781611972825.15"},{"key":"2_CR9","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, UC Berkeley (1984)"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A.: An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, pp. 217\u2013226 (2014)","DOI":"10.1137\/1.9781611973402.16"},{"issue":"4","key":"2_CR11","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.\u00a036(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"2_CR12","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)"},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1994.1032","volume":"17","author":"G. Kortsarz","year":"1994","unstructured":"Kortsarz, G., Peleg, D.: Generating sparse 2-spanners. J. Algorithms\u00a017(2), 222\u2013236 (1994)","journal-title":"J. Algorithms"},{"key":"2_CR14","volume-title":"Combinatorial optimization - networks and matroids","author":"E. Lawler","year":"1976","unstructured":"Lawler, E.: Combinatorial optimization - networks and matroids. Holt, Rinehart and Winston, New York (1976)"},{"issue":"3","key":"2_CR15","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"D.W. Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM\u00a030(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Rangapuram, S.S., B\u00fchler, T., Hein, M.: Towards realistic team formation in social networks based on densest subgraphs. In: Proceedings of the 22nd International Conference on World Wide Web, WWW 2013, pp. 1077\u20131088 (2013)","DOI":"10.1145\/2488388.2488482"},{"key":"2_CR17","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)"},{"key":"2_CR18","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer (2003)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Sherman, J.: Nearly maximum flows in nearly linear time. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October 26-29, pp. 263\u2013269 (2013)","DOI":"10.1109\/FOCS.2013.36"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Sozio, M., Gionis, A.: The community-search problem and how to plan a successful cocktail party. In: KDD, pp. 939\u2013948 (2010)","DOI":"10.1145\/1835804.1835923"}],"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-319-15612-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T12:14:54Z","timestamp":1651320894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-15612-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319156118","9783319156125"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15612-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}