{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T12:14:24Z","timestamp":1680437664675},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,3,7]],"date-time":"2012-03-07T00:00:00Z","timestamp":1331078400000},"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":[[2013,11]]},"DOI":"10.1007\/s10878-012-9465-z","type":"journal-article","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T19:45:45Z","timestamp":1331063145000},"page":"723-754","source":"Crossref","is-referenced-by-count":1,"title":["The density maximization problem in graphs"],"prefix":"10.1007","volume":"26","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","published-online":{"date-parts":[[2012,3,7]]},"reference":[{"issue":"4","key":"9465_CR1","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon N, Yuster R, Zwick U (1995) Color-coding. J ACM 42(4):844\u2013856","journal-title":"J ACM"},{"key":"9465_CR2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S1570-8667(03)00033-9","volume":"1","author":"V B\u00e1lint","year":"2003","unstructured":"B\u00e1lint V (2003) The non-approximability of bicriteria network design problems. J Discrete Algorithms 1:339\u2013355","journal-title":"J Discrete Algorithms"},{"key":"9465_CR3","first-page":"226","volume-title":"STOC\u201993: Proceedings of the 25th annual ACM symposium on theory of computing","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender HL (1993) A linear time algorithm for finding tree-decompositions of small treewidth. In: STOC\u201993: Proceedings of the 25th annual ACM symposium on theory of computing. ACM, New York, pp\u00a0226\u2013234"},{"issue":"4","key":"9465_CR4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/net.3230070405","volume":"7","author":"R Chandrasekaran","year":"1977","unstructured":"Chandrasekaran R (1977) Minimal ratio spanning trees. Networks 7(4):335\u2013342","journal-title":"Networks"},{"key":"9465_CR5","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10479-007-0186-0","volume":"154","author":"A Chinchuluun","year":"2007","unstructured":"Chinchuluun A, Pardalos P (2007) A survey of recent developments in multiobjective optimization. Ann Oper Res 154:29\u201350","journal-title":"Ann Oper Res"},{"issue":"2","key":"9465_CR6","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/S0097539704440430","volume":"34","author":"KM Chung","year":"2005","unstructured":"Chung KM, Lu HI (2005) An optimal algorithm for the maximum-density segment problem. SIAM J Comput 34(2):373\u2013387","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"9465_CR7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor Comput Sci 141(1\u20132):109\u2013131","journal-title":"Theor Comput Sci"},{"issue":"3","key":"9465_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S Dreyfus","year":"1971","unstructured":"Dreyfus S, Wagner R (1971) The Steiner problem in graphs. Networks 1(3):195\u2013207","journal-title":"Networks"},{"key":"9465_CR9","first-page":"632","volume-title":"Proc 6th ann ACM-SIAM sympos disc alg","author":"D Eppstein","year":"1995","unstructured":"Eppstein D (1995) Subgraph isomorphism in planar graphs and related problems. In: Proc 6th ann ACM-SIAM sympos disc alg SIAM, Philadelphia, pp\u00a0632\u2013640"},{"key":"9465_CR10","first-page":"434","volume-title":"Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, SODA\u201990","author":"HN Gabow","year":"1990","unstructured":"Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, SODA\u201990. Society for Industrial and Applied Mathematics, Philadelphia, pp\u00a0434\u2013443"},{"key":"9465_CR11","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. Freeman, New York"},{"issue":"2","key":"9465_CR12","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/j.jcss.2004.08.001","volume":"70","author":"MH Goldwasser","year":"2005","unstructured":"Goldwasser MH, Kao MY, Lu HI (2005) Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J Comput Syst Sci 70(2):128\u2013144","journal-title":"J Comput Syst Sci"},{"issue":"5","key":"9465_CR13","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/j.ipl.2007.08.031","volume":"105","author":"SY Hsieh","year":"2008","unstructured":"Hsieh SY, Cheng CS (2008) Finding a maximum-density path in a tree under the weight and length constraints. Inf Process Lett 105(5):202\u2013205","journal-title":"Inf Process Lett"},{"key":"9465_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"944","DOI":"10.1007\/11602613_94","volume-title":"Algorithms and computation","author":"SY Hsieh","year":"2005","unstructured":"Hsieh SY, Chou TY (2005) Finding a weight-constrained maximum-density subtree in a tree. In: Algorithms and computation. LNCS, vol\u00a03827. Springer, Berlin, pp\u00a0944\u2013953"},{"issue":"3","key":"9465_CR15","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/S0022-2836(66)80037-2","volume":"18","author":"RB Inman","year":"1966","unstructured":"Inman RB (1966) A denaturation map of the lambda phage DNA molecule determined by electron microscopy. J Mol Biol 18(3):464\u2013476","journal-title":"J Mol Biol"},{"key":"9465_CR16","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D Karger","year":"1997","unstructured":"Karger D, Motwani R, Ramkumar G (1997) On approximating the longest path in a graph. Algorithmica 18:82\u201398","journal-title":"Algorithmica"},{"key":"9465_CR17","series-title":"LNCS","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and approximations","author":"T Kloks","year":"1994","unstructured":"Kloks T (1994) Treewidth, Computations and approximations. LNCS. Springer, Berlin"},{"issue":"4","key":"9465_CR18","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.disopt.2006.06.002","volume":"3","author":"HC Lau","year":"2006","unstructured":"Lau HC, Ngo TH, Nguyen BN (2006) Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics. Discrete Optim 3(4):385\u2013391","journal-title":"Discrete Optim"},{"issue":"3","key":"9465_CR19","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00453-007-9023-8","volume":"53","author":"DT Lee","year":"2009","unstructured":"Lee DT, Lin TC, Lu HI (2009) Fast algorithms for the density finding problem. Algorithmica 53(3):298\u2013313","journal-title":"Algorithmica"},{"issue":"3","key":"9465_CR20","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/S0022-0000(02)00010-7","volume":"65","author":"YL Lin","year":"2002","unstructured":"Lin YL, Jiang T, Chao KM (2002) Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J Comput Syst Sci 65(3):570\u2013586","journal-title":"J Comput Syst Sci"},{"issue":"1\u20133","key":"9465_CR21","first-page":"349","volume":"407","author":"HF Liu","year":"2008","unstructured":"Liu HF, Chao KM (2008) 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 407(1\u20133):349\u2013358","journal-title":"Theor Comput Sci"},{"key":"9465_CR22","unstructured":"Lokshtanov D (2009) New methods in parameterized algorithms and complexity. PhD thesis, University of Bergen Norway"},{"issue":"1","key":"9465_CR23","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0022-2836(76)80105-2","volume":"108","author":"G Macaya","year":"1976","unstructured":"Macaya G, Thiery JP, Bernardi G (1976) An approach to the organization of eukaryotic genomes at a macromolecular level. J Mol Biol 108(1):237\u2013254","journal-title":"J Mol Biol"},{"issue":"1","key":"9465_CR24","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"MV Marathe","year":"1998","unstructured":"Marathe MV, Ravi R, Sundaram R, Ravi SS, Rosenkrantz DJ, Hunt HB (1998) Bicriteria network design problems. J Algorithms 28(1):142\u2013171","journal-title":"J Algorithms"},{"issue":"2","key":"9465_CR25","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"EM McCreight","year":"1985","unstructured":"McCreight EM (1985) Priority search trees. SIAM J Comput 14(2):257\u2013276","journal-title":"SIAM J Comput"},{"issue":"2","key":"9465_CR26","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"MH Overmars","year":"1981","unstructured":"Overmars MH, van Leeuwen J (1981) Maintenance of configurations in the plane. J Comput Syst Sci 23(2):166\u2013204","journal-title":"J Comput Syst Sci"},{"key":"9465_CR27","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R Ravi","year":"1996","unstructured":"Ravi R, Sundaram R, Marathe MV, Rosenkrantz DJ, Ravi SS (1996) Spanning trees\u2014short or small. SIAM J Discrete Math 9:178\u2013200","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"9465_CR28","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson N, Seymour PD (1984) Graph minors. iii. Planar tree-width. J Comb Theory, Ser B 36(1):49\u201364","journal-title":"J Comb Theory, Ser B"},{"issue":"1","key":"9465_CR29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson N, Seymour PD (1995) Graph minors. XIII. The disjoint paths problem. J Comb Theory, Ser B 63(1):65\u2013110","journal-title":"J Comb Theory, Ser B"},{"key":"9465_CR30","first-page":"770","volume-title":"Proceedings of the eleventh annual ACM\u2013SIAM symposium on discrete algorithms, SODA\u201900","author":"G Robins","year":"2000","unstructured":"Robins G, Zelikovsky A (2000) Improved steiner tree approximation in graphs. In: Proceedings of the eleventh annual ACM\u2013SIAM symposium on discrete algorithms, SODA\u201900. Society for Industrial and Applied Mathematics, Philadelphia, pp\u00a0770\u2013779"},{"key":"9465_CR31","unstructured":"Schuurman P, Woeginger G (2011) Approximation schemes\u2014a tutorial. URL www.win.tue.nl\/~gwoegi\/papers\/ptas.pdf . Preliminary version of a chapter in the book Lectures on Scheduling, to appear"},{"issue":"17","key":"9465_CR32","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1016\/j.ipl.2009.05.005","volume":"109","author":"BY Wu","year":"2009","unstructured":"Wu BY (2009) An optimal algorithm for the maximum-density path in a tree. Inf Process Lett 109(17):975\u2013979","journal-title":"Inf Process Lett"},{"issue":"2","key":"9465_CR33","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0020-0190(98)00194-X","volume":"69","author":"BY Wu","year":"1999","unstructured":"Wu BY, Chao KM, Tang CY (1999) An efficient algorithm for the length-constrained heaviest path problem on a tree. Inf Process Lett 69(2):63\u201367","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9465-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9465-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9465-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:23:17Z","timestamp":1559276597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9465-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,7]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["9465"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9465-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,7]]}}}