{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:52:29Z","timestamp":1758268349998},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_128","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:38Z","timestamp":1330292198000},"page":"149-160","source":"Crossref","is-referenced-by-count":7,"title":["Using sparsification for parametric minimum spanning tree problems"],"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"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"14_CR1","volume-title":"Intersection and Decomposition Algorithms for Planar Arrangements","author":"P.K. Agarwal","year":"1991","unstructured":"P.K. Agarwal. Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, Cambridge, 1991."},{"key":"14_CR2","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_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01589104","volume":"45","author":"P.M. Camerini","year":"1989","unstructured":"P.M. Camerini, F. Maffioli, and C. Vercellis. Multi-constrained matroidal knapsack problems. Mathematical Programming 45:211\u2013231, 1989.","journal-title":"Mathematical Programming"},{"key":"14_CR4","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_CR5","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_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/net.3230070405","volume":"7","author":"R. Chandrasekaran","year":"1977","unstructured":"R. Chandrasekaran. Minimal ratio spanning trees. Networks, 7:335\u2013342, 1977.","journal-title":"Networks"},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. Assoc. Comput. Mach., 39:1\u201354, 1992.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990."},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"M.J. Eisner","year":"1976","unstructured":"M.J. Eisner and D.G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. J. Assoc. Comput. Mach., 23:619\u2013635, 1976.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification \u2014 a technique for speeding up dynamic graph algorithms. In Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 60\u201369, 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"14_CR11","series-title":"Tech Report","volume-title":"Improved sparsification","author":"D. Eppstein","year":"1993","unstructured":"D. Eppstein, Z. Galil, and G.F. Italiano. Improved sparsification. Tech Report 93-20, Department of Computer Science, University of Califonia, Irvine, April, 1993."},{"key":"14_CR12","series-title":"Tech. Rep.","volume-title":"Choosing subsets with maximum weighted average","author":"D. Eppstein","year":"1995","unstructured":"D. Eppstein and D. S. Hirschberg. Choosing subsets with maximum weighted average. Tech. Rep. 95-12, Dept. Inf. and Comp. Sci., UC Irvine, 1995."},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"D. Eppstein. Geometric lower bounds for parametric matroid optimization. In 27th Annual Symp. on Theory of Computing, pp. 662\u2013671, 1995.","DOI":"10.1145\/225058.225284"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"D. Fern\u00e1ndez-Baca and G. Slutzki. Optimal parametric search on graphs of bounded tree-width. In Proc. 4th Scandinavian Workshop on Algorithm Theory, pp. 155\u2013166, LNCS 824, Springer-Verlag, 1994. To appear in J. Algorithms.","DOI":"10.1007\/3-540-58218-5_14"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"D. Fern\u00e1ndez-Baca and G. Slutzki. Linear-time algorithms for parametric minimum spanning tree problems on planar graphs. In Proc. Latin American Conference on Theoretical Informatics, pp. 257\u2013271, LNCS 911, Springer-Verlag, 1995.","DOI":"10.1007\/3-540-59175-3_94"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"G.N. Frederickson. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14:781\u2013798, 1985.","journal-title":"SIAM J. Comput."},{"key":"14_CR17","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_CR18","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson. Ambivalent data structures for dynamic 2-edge connectivity and k-smallest spanning trees. In Proc. 32nd Annual Symp. on Foundations of Computer Science, pp. 632\u2013641, 1991.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"M. Fredman and D. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In Proc. 31st Annual IEEE Symp. on Foundations of Computer Science, 1990, pp. 719\u2013725.","DOI":"10.1109\/FSCS.1990.89594"},{"key":"14_CR20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"H.N. Gabow, Z. Galil, T. Spencer, and R.E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6:109\u2013122, 1986.","journal-title":"Combinatorica"},{"key":"14_CR21","series-title":"Technical Report UCB\/ERL","volume-title":"Sensitivity analysis for combinatorial optimization","author":"D. Gusfield","year":"1980","unstructured":"D. Gusfield. Sensitivity analysis for combinatorial optimization. Technical Report UCB\/ERL M80\/22, University of California, Berkeley, May 1980."},{"issue":"3","key":"14_CR22","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1145\/2402.322391","volume":"30","author":"D. Gusfield","year":"1983","unstructured":"D. Gusfield. Parametric combinatorial computing and a problem in program module allocation. J. Assoc. Comput. Mach., 30(3):551\u2013563, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR23","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1287\/moor.14.2.362","volume":"14","author":"R. Hassin","year":"1989","unstructured":"R. Hassin and A. Tamir. Maximizing classes of two-parametric objectives over matroids. Math. Oper. Res., 14:362\u2013375, 1989.","journal-title":"Math. Oper. Res."},{"key":"14_CR24","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0166-218X(81)90004-4","volume":"3","author":"H. Ishii","year":"1981","unstructured":"H. Ishii, S. Shiode, and T. Nishida. Stochastic spanning tree problem. Discrete Applied Mathematics, 3:263\u2013273, 1981.","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR25","unstructured":"N. Katoh and T. Ibaraki. On the total number of pivots required for certain parametric combinatorial optimization problems. Technical Report Working Paper 71, Inst. Econ. Res., Kobe Univ. Commerce, 1983."},{"key":"14_CR26","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"D.R. Karger, P.N. Klein, and R.E. Tarjan. A randomized linear-time algorithm for finding minimum spanning trees. J. Assoc. Comput. Mach., 42:321\u2013329, 1995.","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek and O. Schwartzkopf. A deterministic algorithm for the three-dimensional diameter problem. In Proceedings of 25th Annual Symposium on Theory of Computing, pp. 478\u2013484 (1993).","DOI":"10.1145\/167088.167217"},{"key":"14_CR28","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_CR29","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_CR30","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0925-7721(94)90011-6","volume":"4","author":"M. Sharir","year":"1994","unstructured":"M. Sharir and S. Toledo. Extremal polygon containment problems. Computational Geometry, 4:99\u2013118, 1994.","journal-title":"Computational Geometry"},{"issue":"3","key":"14_CR31","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D.K. Sleator","year":"1983","unstructured":"D.D.K. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362\u2013391, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR32","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. 74\u201387, World Scientific Press 1993. A preliminary version appeared in FOCS 92.","DOI":"10.1142\/9789814354363_0019"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_128.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:05:59Z","timestamp":1605647159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_128","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}