{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T05:48:39Z","timestamp":1748929719232},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642226847"},{"type":"electronic","value":"9783642226854"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22685-4_3","type":"book-chapter","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T08:54:39Z","timestamp":1312966479000},"page":"25-36","source":"Crossref","is-referenced-by-count":1,"title":["The Density Maximization Problem in Graphs"],"prefix":"10.1007","author":[{"given":"Mong-Jen","family":"Kao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bastian","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Krug","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. T.","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/S1570-8667(03)00033-9","volume":"1","author":"V. B\u00e1lint","year":"2003","unstructured":"B\u00e1lint, V.: The non-approximability of bicriteria network design problems. J. of Discrete Algorithms\u00a01, 339\u2013355 (2003)","journal-title":"J. of Discrete Algorithms"},{"key":"3_CR2","first-page":"226","volume-title":"STOC 1993: Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: STOC 1993: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp. 226\u2013234. ACM, New York (1993)"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10479-007-0186-0","volume":"154","author":"A. Chinchuluun","year":"2007","unstructured":"Chinchuluun, A., Pardalos, P.: A survey of recent developments in multiobjective optimization. Annals of Operations Research\u00a0154, 29\u201350 (2007)","journal-title":"Annals of Operations Research"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0097539704440430","volume":"34","author":"K.-M. Chung","year":"2005","unstructured":"Chung, K.-M., Lu, H.-I.: An optimal algorithm for the maximum-density segment problem. SIAM J. Comput.\u00a034(2), 373\u2013387 (2005)","journal-title":"SIAM J. Comput."},{"key":"3_CR5","first-page":"632","volume-title":"Proc. 6th Ann. ACM-SIAM Sympos. Disc. Alg.","author":"D. Eppstein","year":"1995","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc. 6th Ann. ACM-SIAM Sympos. Disc. Alg., pp. 632\u2013640. SIAM, Philadelphia (1995)"},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.jcss.2004.08.001","volume":"70","author":"M.H. Goldwasser","year":"2005","unstructured":"Goldwasser, M.H., Kao, M.-Y., Lu, H.-I.: Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J. Comput. Syst. Sci.\u00a070(2), 128\u2013144 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"3_CR7","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.ipl.2007.08.031","volume":"105","author":"S.-Y. Hsieh","year":"2008","unstructured":"Hsieh, S.-Y., Cheng, C.-S.: Finding a maximum-density path in a tree under the weight and length constraints. Information Processing Letters\u00a0105(5), 202\u2013205 (2008)","journal-title":"Information Processing Letters"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1007\/11602613_94","volume-title":"Algorithms and Computation","author":"S.-Y. Hsieh","year":"2005","unstructured":"Hsieh, S.-Y., Chou, T.-Y.: Finding a Weight-Constrained Maximum-Density Subtree in a Tree. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 944\u2013953. Springer, Heidelberg (2005)"},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/S0022-2836(66)80037-2","volume":"18","author":"R.B. Inman","year":"1966","unstructured":"Inman, R.B.: A denaturation map of the lambda phage DNA molecule determined by electron microscopy. Journal of Molecular Biology\u00a018(3), 464\u2013476 (1966)","journal-title":"Journal of Molecular Biology"},{"unstructured":"Kao, M.-J., Katz, B., Krug, M., Lee, D.T., Rutter, I., Wagner, D.: The density maximization problem in graphs. Technical Report 2011-2018, Kalrsruhe Institute of Technology, KIT (2011), \n                  \n                    http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000023123","key":"3_CR10"},{"issue":"3","key":"3_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00453-007-9023-8","volume":"53","author":"D.T. Lee","year":"2009","unstructured":"Lee, D.T., Lin, T.-C., Lu, H.-I.: Fast algorithms for the density finding problem. Algorithmica\u00a053(3), 298\u2013313 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"3_CR12","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1016\/S0022-0000(02)00010-7","volume":"65","author":"Y.-L. Lin","year":"2002","unstructured":"Lin, Y.-L., Jiang, T., Chao, K.-M.: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. Syst. Sci.\u00a065(3), 570\u2013586 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2008.06.052","volume":"407","author":"H.-F. Liu","year":"2008","unstructured":"Liu, H.-F., Chao, K.-M.: Algorithms for finding the weight-constrained k longest paths in a tree and the length-constrained k maximum-sum segments of a sequence. Theor. Comput. Sci.\u00a0407(1-3), 349\u2013358 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0022-2836(76)80105-2","volume":"108","author":"G. Macaya","year":"1976","unstructured":"Macaya, G., Thiery, J.-P., Bernardi, G.: An approach to the organization of eukaryotic genomes at a macromolecular level. Journal of Molecular Biology\u00a0108(1), 237\u2013254 (1976)","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"M.V. Marathe","year":"1998","unstructured":"Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Bicriteria network design problems. Journal of Algorithms\u00a028(1), 142\u2013171 (1998)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. Journal of Computer and System Sciences\u00a023(2), 166\u2013204 (1981)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Schuurman, P., Woeginger, G.: Approximation schemes \u2013 a tutorial. Preliminary version of a chapter in the book \u201dLectures on Scheduling\u201d, (to appear, 2011)","key":"3_CR17"},{"issue":"17","key":"3_CR18","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1016\/j.ipl.2009.05.005","volume":"109","author":"B.Y. Wu","year":"2009","unstructured":"Wu, B.Y.: An optimal algorithm for the maximum-density path in a tree. Inf. Process. Lett.\u00a0109(17), 975\u2013979 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"3_CR19","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(98)00194-X","volume":"69","author":"B.Y. Wu","year":"1999","unstructured":"Wu, B.Y., Chao, K.-M., Tang, C.Y.: An efficient algorithm for the length-constrained heaviest path problem on a tree. Inf. Process. Lett.\u00a069(2), 63\u201367 (1999)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22685-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T09:18:12Z","timestamp":1554023892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22685-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642226847","9783642226854"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22685-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}