{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:11:59Z","timestamp":1725455519292},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620488"},{"type":"electronic","value":"9783540496335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0009487","type":"book-chapter","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T14:32:17Z","timestamp":1129818737000},"page":"115-125","source":"Crossref","is-referenced-by-count":3,"title":["Computing fair and bottleneck matchings in geometric graphs"],"prefix":"10.1007","author":[{"given":"Alon","family":"Efrat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,10,11]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0925-7721(92)90017-M","volume":"2","author":"P.K. Agarwal","year":"1992","unstructured":"P.K. Agarwal and J. Matou\u0161ek, Relative neighborhood graphs in three dimensions, Comp. Geom. Theory and App. 2 (1992), 1\u201314.","journal-title":"Comp. Geom. Theory and App."},{"key":"12_CR2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0925-7721(92)90001-9","volume":"1","author":"P.K. Agarwal","year":"1992","unstructured":"P.K. Agarwal, J. Matou\u0161ek and S. Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Comp. Geom. Theory and App. 1 (1992), 189\u2013201.","journal-title":"Comp. Geom. Theory and App."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"P.K. Agarwal, A. Efrat and M. Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings 11 Annual Symposium on Computational Geometry, 1995, 39\u201350.","DOI":"10.1145\/220279.220284"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01758842","volume":"8","author":"M.S. Chang","year":"1992","unstructured":"M.S. Chang, C.Y. Tang, and R.C.T. Lee, Solving the Euclidean bottleneck matching problem by k-relative neighborhood graphs, Algorithmica 8 (1992), 177\u2013194.","journal-title":"Algorithmica"},{"key":"12_CR5","unstructured":"L.P. Chew, D. Dor, A. Efrat and K. Kedem, Geometric pattern matching in d-dimensional space, ESA '95, LNCS 979, 264\u2013279."},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"L.P. Chew and K. Kedem, Improvements on geometric pattern matching problems, SWAT'92, LNCS 621, 318\u2013325.","DOI":"10.1007\/3-540-55706-7_28"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"A. Efrat and A. Itai, Improvements on bottleneck matching and related problems using geometry, Proceedings 12 Annual Symposium on Computational Geometry, 1996, 301\u2013310.","DOI":"10.1145\/237218.237399"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"G.N. Frederickson and D.B. Johnson, Generalized selection and ranking sorted matrices, SIAM J. Computing 13 (1984), 14\u201330.","journal-title":"SIAM J. Computing"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"9","author":"H.N. Gabow","year":"1988","unstructured":"H.N. Gabow and R.E. Tarjan, Algorithms for two bottleneck optimization problems, J. Algorithms 9 (1988), 411\u2013417.","journal-title":"J. Algorithms"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0166-218X(88)90062-5","volume":"20","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and B. Schieber, On finding most uniform spanning trees, Disc. App. Mathematics 20 (1988), 173\u2013175.","journal-title":"Disc. App. Mathematics"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0167-6377(88)90029-6","volume":"7","author":"S.K. Gupta","year":"1988","unstructured":"S.K. Gupta and A.P. Punnen, Minimum deviation problems, Oper. Res. Lett. 7 (1988), 201\u2013204.","journal-title":"Oper. Res. Lett."},{"key":"12_CR12","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF02574383","volume":"12","author":"D. Halperin","year":"1994","unstructured":"D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility of terrains, Disc and Comp. Geom 12 (1994), 313\u2013326.","journal-title":"Disc and Comp. Geom"},{"key":"12_CR13","first-page":"93","volume":"8","author":"P.J. Heffernan","year":"1992","unstructured":"P.J. Heffernan and S. Schirra, Approximate decision algorithms for point set congruence, SIAM J. Computings 8 (1992), 93\u2013101.","journal-title":"SIAM J. Computings"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"P.J. Heffernan, Generalized approximate algorithms for point set congruence, WADS'93, LNCS 709, 373\u2013384.","DOI":"10.1007\/3-540-57155-8_263"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"J. Hopcroft and R.M. Karp, An n 5\/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Computing 2 (1973), 225\u2013231.","journal-title":"SIAM J. Computing"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"M. Katz, Improved algorithms in geometric optimization via expanders, Proc. 3rd Israel Symp. on Theory of Computing and Systems, 1995, 78\u201387. (See also, M.J. Katz and M. Sharir, An expander-based approach to geometric optimization, SIAM J. Computing, to appear.)","DOI":"10.1109\/ISTCS.1995.377043"},{"key":"12_CR17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H. Kuhn","year":"1955","unstructured":"H. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2 (1955), 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"key":"12_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New-York, 1976."},{"key":"12_CR19","first-page":"259","volume":"31","author":"S. Martello","year":"1987","unstructured":"S. Martello and P. Toth, Linear assignment problems, Annals of Disc. Mathematics 31 (1987), 259\u2013282.","journal-title":"Annals of Disc. Mathematics"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"S. Micali and V.V. Vazirani, An O(\u221a\u00a6V\u00a6 \u00b7 \u00a6E\u00a6) algorithm for finding maximum matching in general graphs, Proc. 21 Annual ACM Symp. on Theory of Comp., 1980, 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"12_CR21","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M. Sharir","year":"1994","unstructured":"M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Disc and Comp Geom 12 (1994), 327\u2013345.","journal-title":"Disc and Comp Geom"},{"key":"12_CR22","first-page":"66","volume":"450","author":"T.H. Su","year":"1990","unstructured":"T.H. Su and R.C. Chang, The k-Gabriel graphs and their applications, 1st Annual SIGAL International Symp. Algorithms, LNCS 450, 1990, 66\u201375.","journal-title":"LNCS"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"P.M. Vaidya","year":"1989","unstructured":"P.M. Vaidya, Geometry helps in matching, SIAM J. Computing 18 (1989), 1201\u20131225.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0009487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T11:13:15Z","timestamp":1586517195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0009487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620488","9783540496335"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0009487","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}