{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:18Z","timestamp":1725664098490},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_14","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:11Z","timestamp":1330270631000},"page":"155-166","source":"Crossref","is-referenced-by-count":2,"title":["Optimal parametric search on graphs of bounded tree-width"],"prefix":"10.1007","author":[{"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giora","family":"Slutzki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"14_CR1","unstructured":"R. Agarwala and D. Fern\u00e1ndez-Baca. Weighted multidimensional search and its application to convex optimization. DIMACS Technical Report 92-51, November, 1992. To appear in SIAM J. Comput.."},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12:308\u2013340.","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. In Proceedings of 24th Annual Symposium on Foundations of Computer Science, pp. 265\u2013273, 1983.","DOI":"10.1109\/SFCS.1983.7"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M. W. Bern","year":"1987","unstructured":"M.W. Bern, E.L. Lawler, and A.L. Wong. Linear time computation of optimal subgraphs of decomposable graphs. J. Algorithms, 8:216\u2013235, 1987.","journal-title":"J. Algorithms"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R. B. Borie","year":"1992","unstructured":"R.B. Borie, R.G. Parker, and C.A. Tovey. Automatic generation of linear-time algorithms from predicate-calculus descriptions of problems on recursively-constructed graph families. Algorithmica, 7:555\u2013582, 1992.","journal-title":"Algorithmica"},{"key":"14_CR6","first-page":"116","volume":"36","author":"H. L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender. Some classes of graphs with bounded tree-width. Bulletin of the EATCS, 36 (1988), 116\u2013126.","journal-title":"Bulletin of the EATCS"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small tree-width. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp. 226\u2013233, 1993.","DOI":"10.1145\/167088.167161"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair, and parametric searching. In Proceedings of the 8th Annual ACM Symposium on Computational Geometry, pp. 120\u2013129 (1992).","DOI":"10.1145\/142675.142702"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"E. Cohen and N. Megiddo. Maximizing concave functions in fixed dimension. In Complexity in Numerical Computations, P.M. Pardalos, ed., pp. 74\u201387, World Scientific Press 1993.","DOI":"10.1142\/9789814354363_0005"},{"issue":"1","key":"14_CR10","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. J. Assoc. Comput. Mach., 34(1):200\u2013208, 1987.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1006\/jagm.1994.1019","volume":"16","author":"D. Fern\u00e1ndez-Baca","year":"1994","unstructured":"D. Fern\u00e1ndez-Baca and G. Slutzki. Parametric problems on graphs of bounded tree-width. J. Algorithms, 16:408\u2013430 (1994).","journal-title":"J. Algorithms"},{"key":"14_CR12","unstructured":"G.N. Frederickson. Optimal algorithms for partitioning trees and locating p-centers in trees. Technical Report CSD-TR 1029, Department of Computer Science, Purdue University, October 1990."},{"key":"14_CR13","unstructured":"G.N. Frederickson. Maintaining regular properties in k-terminal graphs. Manuscript, 1993."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich and R. Tamassia. Dynamic trees and dynamic point location. In Proceedings of the 23rd Annual Symposium on Theory of Computing, 1991, pp. 523\u2013533.","DOI":"10.1145\/103418.103472"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"J. Lagergren. Efficient parallel algorithms for tree-decomposition and related problems. In Proceedings of 31st Annual Symposium on Foundations of Computer Science, pp. 173\u2013182 (1990).","DOI":"10.1109\/FSCS.1990.89536"},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"N. Megiddo. Combinatorial optimization with rational objective functions. Math. Oper. Res., 4:414\u2013424 (1979).","journal-title":"Math. Oper. Res."},{"issue":"4","key":"14_CR17","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach., 30(4):852\u2013865, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"B. Reed. Finding approximate separators and computing tree-width quickly. Proceedings of 24th Annual Symposium on Theory of Computing, pp. 221\u2013228, 1992.","DOI":"10.1145\/129712.129734"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors II: Algorithmic aspects of tree-width. J. Algorithms, 7:309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"14_CR20","volume-title":"Handbook of Theoretical Computer Science","author":"J. Leeuwen van","year":"1990","unstructured":"J. van Leeuwen. Graph Algorithms. In J. van Leeuwen (ed.) Handbook of Theoretical Computer Science, MIT Press, Cambridge, Mass., 1990."},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26:362\u2013391 (1983).","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"S. Toledo. Maximizing non-linear convex functions in fixed dimension. In Complexity in Numerical Computations, P.M. Pardalos, ed., pp. 429\u2013446. World Scientific Press 1993.","DOI":"10.1142\/9789814354363_0019"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"S. Toledo. Approximate parametric searching. Manuscript, 1993.","DOI":"10.1016\/0020-0190(93)90149-4"},{"key":"14_CR24","unstructured":"T.V. Wimer. Linear algorithms on k-terminal graphs. Ph.D. Thesis, Report No. URI-030, Clemson University (1987)."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:44Z","timestamp":1605647924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}