{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T11:14:15Z","timestamp":1742642055201,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-LABX-0070","ANR-11-IDEX-0007"],"award-info":[{"award-number":["ANR-10-LABX-0070","ANR-11-IDEX-0007"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0297","J1-1693","J1-8130","J1-8155","J1-9109"],"award-info":[{"award-number":["P1-0297","J1-1693","J1-8130","J1-8155","J1-9109"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["R611450"],"award-info":[{"award-number":["R611450"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010198","name":"Ministerio de Econom\u00eda, Industria y Competitividad, Gobierno de Espa\u00f1a","doi-asserted-by":"publisher","award":["MTM2017-86767-R"],"award-info":[{"award-number":["MTM2017-86767-R"]}],"id":[{"id":"10.13039\/501100010198","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00453-020-00716-4","type":"journal-article","created":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T17:04:17Z","timestamp":1589821457000},"page":"3018-3040","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Inverse Voronoi Problem in Graphs I: Hardness"],"prefix":"10.1007","volume":"82","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3183-4126","authenticated-orcid":false,"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hebert","family":"P\u00e9rez-Ros\u00e9s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Aloupis, G., P\u00e9rez-Ros\u00e9s, H., Pineda-Villavicencio, G., Taslakian, P., Trinchet-Almaguer, D.: Fitting Voronoi diagrams to planar tesselations. In: Combinatorial Algorithms\u201424th International Workshop, IWOCA Lecture Notes in Computer Science, vol. 8288. Springer,, pp.\u00a0349\u2013361 (2013). https:\/\/doi.org\/10.1007\/978-3-642-45278-9_30","key":"716_CR1","DOI":"10.1007\/978-3-642-45278-9_30"},{"issue":"2","key":"716_CR2","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF00181470","volume":"19","author":"PF Ash","year":"1985","unstructured":"Ash, P.F., Bolker, E.D.: Recognizing Dirichlet tessellations. Geom. Dedic. 19(2), 175\u2013206 (1985). https:\/\/doi.org\/10.1007\/BF00181470","journal-title":"Geom. Dedic."},{"key":"716_CR3","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.tcs.2014.10.003","volume":"562","author":"S Bandyapadhyay","year":"2015","unstructured":"Bandyapadhyay, S., Banik, A., Das, S., Sarkar, H.: Voronoi game on graphs. Theor. Comput. Sci. 562, 270\u2013282 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.10.003","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Banerjee, S., Bhattacharya, B.B., Das, S., Karmakar, A., Maheshwari, A., Roy, S.: On the construction of generalized Voronoi inverse of a rectangular tessellation. Transactions on Computational Science. Lecture Notes in Computer Science, vol. 8110. Springer, pp.\u00a022\u201338 (2013). https:\/\/doi.org\/10.1007\/978-3-642-41905-8_3","key":"716_CR4","DOI":"10.1007\/978-3-642-41905-8_3"},{"doi-asserted-by":"crossref","unstructured":"Biniaz, A., Cabello, S., Carmi, P., De Carufel, J., Maheshwari, A., Mehrabi, S., Smid, M.: On the minimum consistent subset problem. CoRR arXiv:1810.09232 (2018)","key":"716_CR5","DOI":"10.1007\/978-3-030-24766-9_12"},{"unstructured":"Bonnet, \u00c9., Cabello, S., Mohar, B., P\u00e9rez-Ros\u00e9s, H.: The inverse Voronoi problem in graphs II: trees (2018). Manuscript. Its content is included in arXiv:1811.12547","key":"716_CR6"},{"unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms (to appear). Preliminary version presented at SODA (2017). Full version available at arXiv:1702.07815","key":"716_CR7"},{"doi-asserted-by":"publisher","unstructured":"Colin de Verdi\u00e8re, \u00c9.: Shortest cut graph of a surface with prescribed vertex set. In: Algorithms - ESA 2010, 18th Annual European Symposium, Part II. Lecture Notes in Computer Science, vol. 6347. Springer, pp.\u00a0100\u2013111 (2010) https:\/\/doi.org\/10.1007\/978-3-642-15781-3_9","key":"716_CR8","DOI":"10.1007\/978-3-642-15781-3_9"},{"key":"716_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"8","key":"716_CR10","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1016\/j.comgeo.2015.04.003","volume":"48","author":"TK Dey","year":"2015","unstructured":"Dey, T.K., Fan, F., Wang, Y.: Graph induced complex on point data. Comput. Geom. 48(8), 575\u2013588 (2015). https:\/\/doi.org\/10.1016\/j.comgeo.2015.04.003","journal-title":"Comput. Geom."},{"key":"716_CR11","volume-title":"Graph Theory Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory Graduate Texts in Mathematics, 4th edn, vol. 173. Springer, Berlin (2012)","edition":"4"},{"doi-asserted-by":"publisher","unstructured":"Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156\u2013163 (2000). https:\/\/doi.org\/10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L","key":"716_CR12","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic $$\\tilde{o}(n^{5\/3})$$ time. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SIAM, pp.\u00a0495\u2013514 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.33. Full version available at arXiv:1704.02793","key":"716_CR13","DOI":"10.1137\/1.9781611975031.33"},{"doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Mozes, S., Weimann, O., Wulff-Nilsen, C.: Better tradeoffs for exact distance oracles in planar graphs. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp.\u00a0515\u2013529 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.34","key":"716_CR14","DOI":"10.1137\/1.9781611975031.34"},{"issue":"3","key":"716_CR15","doi-asserted-by":"publisher","first-page":"439","DOI":"10.7155\/jgaa.00331","volume":"18","author":"D Gerbner","year":"2014","unstructured":"Gerbner, D., M\u00e9sz\u00e1ros, V., P\u00e1lv\u00f6lgyi, D., Pokrovskiy, A., Rote, G.: Advantage in the discrete Voronoi game. J. Graph Algorithms Appl. 18(3), 439\u2013457 (2014). https:\/\/doi.org\/10.7155\/jgaa.00331","journal-title":"J. Graph Algorithms Appl."},{"issue":"6","key":"716_CR16","doi-asserted-by":"publisher","first-page":"4120","DOI":"10.1109\/TIT.2018.2822267","volume":"64","author":"L Gottlieb","year":"2018","unstructured":"Gottlieb, L., Kontorovich, A., Nisnevitch, P.: Near-optimal sample compression for nearest neighbors. IEEE Trans. Inf. Theory 64(6), 4120\u20134128 (2018). https:\/\/doi.org\/10.1109\/TIT.2018.2822267","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"716_CR17","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TIT.1968.1054155","volume":"14","author":"PE Hart","year":"1968","unstructured":"Hart, P.E.: The condensed nearest neighbor rule (corresp.). IEEE Trans. Inf. Theory 14(3), 515\u2013516 (1968). https:\/\/doi.org\/10.1109\/TIT.1968.1054155","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"716_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"716_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"716_CR20","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1145\/3199606","volume":"14","author":"S Kannan","year":"2018","unstructured":"Kannan, S., Mathieu, C., Zhou, H.: Graph reconstruction and verification. ACM Trans. Algorithms 14(4), 40:1\u201340:30 (2018). https:\/\/doi.org\/10.1145\/3199606. Preliminary version in ICALP 2015","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"716_CR21","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"LM Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and seatching. Discrete Math. 55(2), 181\u2013184 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90046-9","journal-title":"Discrete Math."},{"issue":"2","key":"716_CR22","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982). https:\/\/doi.org\/10.1137\/0211025","journal-title":"SIAM J. Comput."},{"issue":"1","key":"716_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a005","journal-title":"Theory Comput."},{"doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. CoRR arXiv:1504.05476 (2015). Preliminary version at ESA 2015","key":"716_CR24","DOI":"10.1007\/978-3-662-48350-3_72"},{"issue":"2","key":"716_CR25","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 11:1\u201311:29 (2008). https:\/\/doi.org\/10.1145\/1346330.1346336","journal-title":"J. ACM"},{"key":"716_CR26","doi-asserted-by":"publisher","DOI":"10.1002\/9781119967101","volume-title":"Spatial Analysis along Networks. Statistical and Computational Methods","author":"A Okabe","year":"2012","unstructured":"Okabe, A., Sugihara, K.: Spatial Analysis along Networks. Statistical and Computational Methods. Wiley, Hoboken (2012)"},{"issue":"6","key":"716_CR27","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1109\/TIT.1975.1055464","volume":"21","author":"GL Ritter","year":"1975","unstructured":"Ritter, G.L., Woodruff, H.B., Lowry, S.R., Isenhour, T.L.: An algorithm for a selective nearest neighbor decision rule (corresp.). IEEE Trans. Inf. Theory 21(6), 665\u2013669 (1975)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00716-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00716-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00716-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,17]],"date-time":"2021-05-17T23:39:05Z","timestamp":1621294745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00716-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["716"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00716-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,5,18]]},"assertion":[{"value":"25 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}