{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:33Z","timestamp":1775912913386,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2017,12,20]],"date-time":"2017-12-20T00:00:00Z","timestamp":1513728000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,12,20]],"date-time":"2017-12-20T00:00:00Z","timestamp":1513728000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["16K16005"],"award-info":[{"award-number":["16K16005"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["26-11908"],"award-info":[{"award-number":["26-11908"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17H07357"],"award-info":[{"award-number":["17H07357"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-017-0400-7","type":"journal-article","created":{"date-parts":[[2017,12,20]],"date-time":"2017-12-20T12:36:46Z","timestamp":1513773406000},"page":"3461-3480","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["The Densest Subgraph Problem with a Convex\/Concave Size Function"],"prefix":"10.1007","volume":"80","author":[{"given":"Yasushi","family":"Kawase","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6033-6433","authenticated-orcid":false,"given":"Atsushi","family":"Miyauchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,20]]},"reference":[{"key":"400_CR1","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":"Reid Andersen","year":"2009","unstructured":"Andersen, R., Chellapilla, K.: Finding dense subgraphs with size bounds. In: WAW\u00a0\u201909: Proceedings of the 6th Workshop on Algorithms and Models for the Web Graph, pp. 25\u201337 (2009)"},{"issue":"6","key":"400_CR2","doi-asserted-by":"publisher","first-page":"574","DOI":"10.14778\/2168651.2168658","volume":"5","author":"Albert Angel","year":"2012","unstructured":"Angel, A., Sarkas, N., Koudas, N., Srivastava, D.: Dense subgraph maintenance under streaming edge weight updates for real-time story identification. In: VLDB\u00a0\u201912: Proceedings of the 38th International Conference on Very Large Data Bases, pp. 574\u2013585 (2012)","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"2","key":"400_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"},{"issue":"1","key":"400_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"GD Bader","year":"2003","unstructured":"Bader, G.D., Hogue, C.W.V.: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinform. 4(1), 1\u201327 (2003)","journal-title":"BMC Bioinform."},{"key":"400_CR5","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\u00a0\u201910: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"400_CR6","doi-asserted-by":"crossref","unstructured":"Bonchi, F., Gullo, F., Kaltenbrunner, A., Volkovich, Y.: Core decomposition of uncertain graphs. In: KDD\u00a0\u201914: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1316\u20131325 (2014)","DOI":"10.1145\/2623330.2623655"},{"key":"400_CR7","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"Moses Charikar","year":"2000","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: APPROX\u00a0\u201900: Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 84\u201395 (2000)"},{"issue":"6","key":"400_CR8","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1137\/S0097539791278376","volume":"25","author":"J Cheriyan","year":"1996","unstructured":"Cheriyan, J., Hagerup, T., Mehlhorn, K.: An $$o(n^3)$$-time maximum-flow algorithm. SIAM J. Comput. 25(6), 1144\u20131170 (1996)","journal-title":"SIAM J. Comput."},{"key":"400_CR9","doi-asserted-by":"crossref","unstructured":"Dourisboure, Y., Geraci, F., Pellegrini, M.: Extraction and classification of dense communities in the web. In: WWW\u00a0\u201907: Proceedings of the 16th International Conference on World Wide Web, pp. 461\u2013470 (2007)","DOI":"10.1145\/1242572.1242635"},{"issue":"3","key":"400_CR10","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"},{"issue":"14","key":"400_CR11","doi-asserted-by":"publisher","first-page":"e150","DOI":"10.1093\/bioinformatics\/btl243","volume":"22","author":"E Fratkin","year":"2006","unstructured":"Fratkin, E., Naughton, B.T., Brutlag, D.L., Batzoglou, S.: MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics 22(14), e150\u2013e157 (2006)","journal-title":"Bioinformatics"},{"key":"400_CR12","volume-title":"Submodular Functions and Optimization, Annals of Discrete Mathematics","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58. Elsevier, Amsterdam (2005)"},{"key":"400_CR13","unstructured":"Gibson, D., Kumar, R., Tomkins, A.: Discovering large dense subgraphs in massive graphs. In: VLDB\u00a0\u201905: Proceedings of the 31st International Conference on Very Large Data Bases, pp. 721\u2013732 (2005)"},{"key":"400_CR14","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, University of California Berkeley (1984)"},{"key":"400_CR15","unstructured":"Kawase, Y., Miyauchi, A.: The densest subgraph problem with a convex\/concave size function. In: ISAAC\u00a0\u201916: Proceedings of the 27th International Symposium on Algorithms and Computation, pp. 44:1\u201344:12 (2016)"},{"issue":"4","key":"400_CR16","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":"400_CR17","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-02927-1_50","volume-title":"Automata, Languages and Programming","author":"Samir Khuller","year":"2009","unstructured":"Khuller, S., Saha, B.: On finding dense subgraphs. In: ICALP\u00a0\u201909: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 597\u2013608 (2009)"},{"key":"400_CR18","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.W.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: FOCS\u00a0\u201915: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1049\u20131065 (2015)","DOI":"10.1109\/FOCS.2015.68"},{"issue":"4","key":"400_CR19","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Math. Oper. Res. 4(4), 414\u2013424 (1979)","journal-title":"Math. Oper. Res."},{"key":"400_CR20","unstructured":"Nagano, K., Kawahara, Y., Aihara, K.: Size-constrained submodular minimization through minimum norm base. In: ICML\u00a0\u201911: Proceedings of the 28th International Conference on Machine Learning, pp. 977\u2013984 (2011)"},{"key":"400_CR21","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.: Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: KDD\u00a0\u201913: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 104\u2013112 (2013)","DOI":"10.1145\/2487575.2487645"},{"issue":"1","key":"400_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21764","volume":"71","author":"Hiroki Yanagisawa","year":"2017","unstructured":"Yanagisawa, H., Hara, S.: Discounted average degree density metric and new algorithms for the densest subgraph problem. Networks. \n                    https:\/\/doi.org\/10.1002\/net.21764\n                    \n                   (in press)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0400-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0400-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0400-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:31:28Z","timestamp":1589697088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0400-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,20]]},"references-count":22,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["400"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0400-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,20]]},"assertion":[{"value":"10 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}