{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:16:02Z","timestamp":1758824162634,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,9,8]],"date-time":"2016-09-08T00:00:00Z","timestamp":1473292800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["339025","239985"],"award-info":[{"award-number":["339025","239985"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ANR CompA","award":["ANR-13-BS02-0001-01"],"award-info":[{"award-number":["ANR-13-BS02-0001-01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0207-y","type":"journal-article","created":{"date-parts":[[2016,9,8]],"date-time":"2016-09-08T15:23:09Z","timestamp":1473348189000},"page":"530-567","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Building Efficient and Compact Data Structures for Simplicial Complexes"],"prefix":"10.1007","volume":"79","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"family":"Karthik C. S.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9bastien","family":"Tavenas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,8]]},"reference":[{"key":"207_CR1","doi-asserted-by":"crossref","unstructured":"Acharya, A., Zhu, H., Shen, K.: Adaptive algorithms for cache-efficient trie search. In: Workshop on Algorithm Engineering and Experimentation ALENEX 99, Baltimore (1999)","DOI":"10.1007\/3-540-48518-X_18"},{"key":"207_CR2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(93)90068-K","volume":"46","author":"A Andersson","year":"1993","unstructured":"Andersson, A., Nilsson, S.: Improved behaviour of tries by adaptive branching. Inf. Process. Lett. 46, 295\u2013300 (1993)","journal-title":"Inf. Process. Lett."},{"key":"207_CR3","doi-asserted-by":"crossref","unstructured":"Appel, A.W., Jacobson, G.J.: The world\u2019s fastest scrabble program. In: Communications of the ACM 31 (1988)","DOI":"10.1145\/42411.42420"},{"issue":"4","key":"207_CR4","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1142\/S0218195912600060","volume":"22","author":"D Attali","year":"2012","unstructured":"Attali, D., Lieutier, A., Salinas, D.: Efficient data structure for representing and simplifying simplicial complexes in high dimensions. Int. J. Comput. Geom. Appl. 22(4), 279\u2013303 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"207_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1051\/ita:2007061","volume":"43","author":"A Badr","year":"2009","unstructured":"Badr, A., Geffert, V., Shipman, I.: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43(1), 69\u201394 (2009)","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"207_CR6","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 360\u2013369 (1997)"},{"key":"207_CR7","unstructured":"Billera, L.J., Bj\u00f6rner, A.: Face numbers of polytopes on complexes. In: Handbook of Discrete and Computational Geometry. CRC Press, pp. 291\u2013310 (1997)"},{"key":"207_CR8","unstructured":"Boissonnat, J-D., Karthik C.S., Tavenas, S.: Building efficient and compact data structures for simplicial complexes. In: Symposium on Computational Geometry, pp. 642\u2013656 (2015)"},{"issue":"3","key":"207_CR9","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1007\/s00453-014-9887-3","volume":"70","author":"J-D Boissonnat","year":"2014","unstructured":"Boissonnat, J.-D., Maria, C.: The simplex tree: an efficient data structure for general simplicial complexes. Algorithmica 70(3), 406\u2013427 (2014)","journal-title":"Algorithmica"},{"key":"207_CR10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2015.12.034","volume":"617","author":"J-D Boissonnat","year":"2016","unstructured":"Boissonnat, J.-D., Mazauric, D.: On the complexity of the representation of simplicial complexes by trees. Theor. Comput. Sci. 617, 28\u201344 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"207_CR11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(00)00292-9","volume":"267","author":"C C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., S\u00e2ntean, N., Yu, S.: Minimal cover-automata for finite languages. Theor. Comput. Sci. 267(1\u20132), 3\u201316 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"207_CR12","doi-asserted-by":"crossref","unstructured":"Carrasco, R., Forcada, M.: Incremental construction and maintenanceof minimal finite-state automata. In: Computational Linguistics, vol. 28 (2002)","DOI":"10.1162\/089120102760173652"},{"key":"207_CR13","doi-asserted-by":"crossref","unstructured":"Comer, D., Sethi, R.: Complexity of trie index construction. In: Proceedings of Foundations of Computer Science, pp. 197-207 (1976)","DOI":"10.1109\/SFCS.1976.11"},{"key":"207_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1162\/089120100561601","volume":"26","author":"J Daciuk","year":"2000","unstructured":"Daciuk, J., Mihov, S., Watson, B., Watson, R.: Incremental construction of minimal acyclic finite-state automata. Comput. Linguist. 26, 3\u201316 (2000)","journal-title":"Comput. Linguist."},{"key":"207_CR15","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: International Symposium on Algorithms and Computation, vol. (1), pp. 403-414 (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"207_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman publishers, Newyork (1979)"},{"key":"207_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M Golumbic","year":"2004","unstructured":"Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, Cambridge (2004)"},{"key":"207_CR18","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Characterisations of nowhere dense graphs. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 21-40 (2013)"},{"key":"207_CR19","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton. In: Theory of Machines and Computations, pp. 189\u2013196 (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"207_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, pp. 85\u2013103. IBM, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"207_CR21","doi-asserted-by":"crossref","unstructured":"Maia, E., Moreira, N., Reis, R.: Incomplete transition complexity of some basic operations. In: International Conference on Current Trends in Theory and Practice of Computer Science, pp. 319\u2013331 (2013)","DOI":"10.1007\/978-3-642-35843-2_28"},{"key":"207_CR22","unstructured":"Maletti, A.: Notes on hyper-minimization. In: Proceedings 13th International Conference Automata and Formal Languages, pp. 34\u201349 (2011)"},{"key":"207_CR23","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc. 9, 541\u2013544 (1958)","journal-title":"Proc. Am. Math. Soc."},{"issue":"1","key":"207_CR24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci. 92(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"207_CR25","doi-asserted-by":"crossref","unstructured":"Sgarbas, K., Fakotakis, N., Kokkinakis, G.: Optimal insertion in deterministic DAWGs. In: Theoretical Computer Science, pp. 103\u2013117 (2003)","DOI":"10.1016\/S0304-3975(02)00571-6"},{"key":"207_CR26","doi-asserted-by":"crossref","unstructured":"Teuhola, J., Raita, T.: Text compression using prediction. In: Proceedings of ACM Conference on Research and Development in Information Retrieval, pp. 97\u2013102 (1986)","DOI":"10.1145\/253168.253192"},{"key":"207_CR27","unstructured":"Yellin, D.: Algorithms for subset testing and finding maximal sets. In: SODA, pp. 386\u2013392 (1992)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0207-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0207-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0207-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T04:30:55Z","timestamp":1568349055000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0207-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,8]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["207"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0207-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,9,8]]}}}