{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:01:56Z","timestamp":1725494516422},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676904"},{"type":"electronic","value":"9783540449850"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_9","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T15:17:33Z","timestamp":1194967053000},"page":"83-96","source":"Crossref","is-referenced-by-count":2,"title":["Data Structures for Maintaining Set Partitions"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Saurabh","family":"Sethia","sequence":"additional","affiliation":[]},{"given":"Steven","family":"Skiena","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S0218195998000175","volume":"8","author":"E. Arkin","year":"1998","unstructured":"E. Arkin, H. Meijer, J. Mitchell, D. Rappaport, and S. Skiena. Decision trees for geometric objects. Int. J. Computational Geometry and Applications, 8:343\u2013363, 1998.","journal-title":"Int. J. Computational Geometry and Applications"},{"key":"9_CR2","unstructured":"Gruia Calinescu. A data structure for maintaining a partition. manuscript, 2000."},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01377183","volume":"12","author":"B. Chazelle","year":"1994","unstructured":"Bernard Chazelle, H. Edelsbrunner, M. Grigni, Leonidas J.Guibas, J. Hershberger, Micha Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulationsAlgorithmica, 12:54\u201368, 1994.","journal-title":"Algorithmica"},{"key":"9_CR4","unstructured":"R. Cole and R. Hariharan. Dynamic LCA queries on trees. In Proc. Tenth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 235\u2013244, 1999."},{"key":"9_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications.","author":"M. Berg de","year":"1997","unstructured":"Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997."},{"key":"9_CR6","unstructured":"P. Dietz, K. Mehlhorn, R. Raman, and C. Uhrig. Lower bounds for set intersection queries. In Proc. Fourth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 194\u2013201, 1993."},{"key":"9_CR7","unstructured":"J. Feigenbaum and S. Kannan. Dynamic graph algorithms. Handbook of Discrete and Combinatorial Mathematics, 1995."},{"key":"9_CR8","unstructured":"R. Freimer, J. Mitchell, and C. Piatko. On the complexity of shattering using arrangements. In CCCG: Canadian Conference in Computational Geometry, 1990."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"L. Guibas and R. Sedgewick. A bichromatic framework for balanced trees. In Proc. 19th IEEE Symp. Foundations of Computer Science, pages 8\u201321, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"9_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BFb0028546","volume-title":"Proc. Fifteenth STACS","author":"M. Habib","year":"1998","unstructured":"M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. In Proc. Fifteenth STACS, pages 25\u201338. Springer-Verlag LNCS, 1998."},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"The theory of machines and computations","author":"J. Hopcroft","year":"1971","unstructured":"J. Hopcroft. An nlogn algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The theory of machines and computations, pages 189\u2013196. Academic Press, New York, 1971."},{"key":"9_CR13","volume-title":"Technical Report B-90-2","author":"J. Matou\u0161ek","year":"1990","unstructured":"J. Matou\u0161ek. More on cutting arrangements and spanning trees with low crossing number. Technical Report B-90-2, Fachbereich Mathematik, Freie Universit\u00e4t Berlin, Berlin, 1990."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"R. Paige and R. Tarjan. Three partition refinement algorithms. SIAM J. Computing, 16:973\u2013989, 1987.","journal-title":"SIAM J. Computing"},{"key":"9_CR15","unstructured":"G. Sazaklis, E. Arkin, J. Mitchell, and S. Skiena. Probe trees for touching character recognition. In Proc. International Conference on Imaging Science, Systems and Technology, (CISST), pages 282\u2013289, Las Vegas, NV, 1998."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"G. Sazaklis, E. Arkin, J. S. B. Mitchell, and S. Skiena. Geometric decision trees for optical character recognition. In Proc. of 13th Annual ACM Symposium on Computational Geometry, pages 490\u2013492, Nice, France, June 1997.","DOI":"10.1145\/262839.263020"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. Tarjan","year":"1975","unstructured":"R. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215\u2013225, 1975.","journal-title":"J. ACM"},{"key":"9_CR18","unstructured":"E. Ukkonen. Constructing suffix trees on-line in linear time. In Intern. Federation of Information Processing (IFIP)\u2019 92, pages 484\u2013492, 1992."},{"key":"9_CR19","unstructured":"D. Yellin. Representing sets with constant time equality testing. In Proc. First ACM-SIAM Symp. Discrete Algorithms (SODA), pages 64\u201373, 1990."},{"key":"9_CR20","unstructured":"D. Yellin. Algorithms for subset testing and finding maximal sets. In Proc. Third ACM-SIAM Symp. Discrete Algorithms (SODA), pages 386\u2013392, 1992."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:41:00Z","timestamp":1556952060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}