{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:50:21Z","timestamp":1762300221354,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031231001"},{"type":"electronic","value":"9783031231018"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-23101-8_26","type":"book-chapter","created":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T20:18:53Z","timestamp":1671481133000},"page":"385-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The k-Centre Problem for\u00a0Classes of\u00a0Cyclic Words"],"prefix":"10.1007","author":[{"given":"Duncan","family":"Adamson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Argyrios","family":"Deligkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir V.","family":"Gusev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/978-3-030-38919-2_48","volume-title":"SOFSEM 2020: Theory and Practice of Computer Science","author":"D Adamson","year":"2020","unstructured":"Adamson, D., Deligkas, A., Gusev, V.V., Potapov, I.: On the hardness of energy minimisation for crystal structure prediction. In: Chatzigeorgiou, A., Dondi, R., Herodotou, H., Kapoutsis, C., Manolopoulos, Y., Papadopoulos, G.A., Sikora, F. (eds.) SOFSEM 2020. LNCS, vol. 12011, pp. 587\u2013596. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_48"},{"key":"26_CR2","doi-asserted-by":"publisher","unstructured":"Adamson, D., Deligkas, A., Gusev, V.V., Potapov, I.: Combinatorial algorithms for multidimensional necklaces (2021). https:\/\/arxiv.org\/abs\/2108.01990, https:\/\/doi.org\/10.48550\/ARXIV.2108.01990","DOI":"10.48550\/ARXIV.2108.01990"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-031-13257-5_2","volume-title":"Descriptional Complexity of Formal Systems, DCFS 2022","author":"D Adamson","year":"2022","unstructured":"Adamson, D.: Ranking binary unlabelled necklaces in polynomial time. In: Han, Y.S., Vaszil, G. (eds.) Descriptional Complexity of Formal Systems, DCFS 2022. LNCS, vol. 13439, pp. 15\u201329. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-13257-5_2"},{"key":"26_CR4","doi-asserted-by":"publisher","unstructured":"Adamson, D., Deligkas, A., Gusev, V.V., Potapov, I.: The complexity of periodic energy minimisation. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 241, pp. 8:1\u20138:15, Dagstuhl, Germany (2022). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/16806, https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2022.8","DOI":"10.4230\/LIPIcs.MFCS.2022.8"},{"key":"26_CR5","doi-asserted-by":"publisher","unstructured":"Adamson, D., Gusev, V.V., Potapov, I., Deligkas, A.: Ranking bracelets in polynomial time. In: Gawrychowski, P., Starikovskaya, T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 191, pp. 4:1\u20134:17. Dagstuhl, Germany (2021). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/13955, https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.4","DOI":"10.4230\/LIPIcs.CPM.2021.4"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-030-13435-8_21","volume-title":"Language and Automata Theory and Applications","author":"M Anselmo","year":"2019","unstructured":"Anselmo, M., Madonia, M., Selmi, C.: Toroidal codes and conjugate pictures. In: Mart\u00edn-Vide, C., Okhotin, A., Shapira, D. (eds.) LATA 2019. LNCS, vol. 11417, pp. 288\u2013301. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-13435-8_21"},{"key":"26_CR7","doi-asserted-by":"publisher","unstructured":"Babai, L.: Local expansion of vertex-transitive graphs and random generation in finite groups. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, New York, NY, USA, pp. 164\u2013174. Association for Computing Machinery (1991). https:\/\/doi.org\/10.1145\/103418.103440","DOI":"10.1145\/103418.103440"},{"key":"26_CR8","doi-asserted-by":"publisher","unstructured":"Bae, M.M., Bose, B.: Gray codes for torus and edge disjoint Hamiltonian cycles. In: Proceedings of the 14th International Parallel and Distributed Processing Symposium, IPDPS 2000, pp. 365\u2013370 (2000). https:\/\/doi.org\/10.1109\/IPDPS.2000.846007","DOI":"10.1109\/IPDPS.2000.846007"},{"key":"26_CR9","doi-asserted-by":"publisher","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. ACM Trans. Algorithms 16(4) (2020). https:\/\/doi.org\/10.1145\/3392720","DOI":"10.1145\/3392720"},{"issue":"1\u20133","key":"26_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0012-365X(92)90699-G","volume":"110","author":"F Chung","year":"1992","unstructured":"Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discret. Math. 110(1\u20133), 43\u201359 (1992)","journal-title":"Discret. Math."},{"key":"26_CR11","first-page":"73","volume":"2003","author":"WW Cohen","year":"2003","unstructured":"Cohen, W.W., Ravikumar, P., Fienberg, S.E., et al.: A comparison of string distance metrics for name-matching tasks. IIWeb 2003, 73\u201378 (2003)","journal-title":"IIWeb"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Collins, C., et al.: Accelerated discovery of two crystal structure types in a complex inorganic phase field. Nature 546(7657), 280 (2017)","DOI":"10.1038\/nature22374"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Feldmann, A.E., Marx, D.: The parameterized hardness of the k-center problem in transportation networks. Algorithmica 82(7), 1989\u20132005 (2020)","DOI":"10.1007\/s00453-020-00683-w"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theory Comput. Syst. 30(2), 113\u2013119 (1997)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"26_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/959242.959248","volume":"5","author":"T G\u00e4rtner","year":"2003","unstructured":"G\u00e4rtner, T.: A survey of kernels for structured data. ACM SIGKDD Explor. Newsl. 5(1), 49\u201358 (2003)","journal-title":"ACM SIGKDD Explor. Newsl."},{"key":"26_CR16","unstructured":"Gasieniec, L., Jansson, J., Lingas, A.: Efficient approximation algorithms for the Hamming Center Problem. In: SODA 1999, pp. 905\u2013906 (1999)"},{"key":"26_CR17","volume-title":"Concrete Mathematics : A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics\u202f: A Foundation for Computer Science. Addison-Wesley, Upper Saddle River (1994)"},{"key":"26_CR18","unstructured":"Hochbaum, D.S.: Approximation algorithms for NP-hard problems. In: Various Notions of Approximations: Good, Better, Best and More (1997)"},{"issue":"4","key":"26_CR19","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1016\/j.disc.2015.11.015","volume":"339","author":"V Horan","year":"2016","unstructured":"Horan, V., Stevens, B.: Locating patterns in the de Bruijn Torus. Discret. Math. 339(4), 1274\u20131282 (2016)","journal-title":"Discret. Math."},{"issue":"1","key":"26_CR20","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0097-3165(93)90087-O","volume":"64","author":"G Hurlbert","year":"1993","unstructured":"Hurlbert, G., Isaak, G.: On the de Bruijn Torus problem. J. Comb. Theory Ser. A 64(1), 50\u201362 (1993)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1","key":"26_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01390770","volume":"6","author":"G Hurlbert","year":"1995","unstructured":"Hurlbert, G., Isaak, G.: New constructions for de Bruijn Tori. Des. Codes Crypt. 6(1), 47\u201356 (1995)","journal-title":"Des. Codes Crypt."},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1006\/jcta.1996.0102","volume":"76","author":"GH Hurlbert","year":"1996","unstructured":"Hurlbert, G.H., Mitchell, C.J., Paterson, K.G.: On the existence of de Bruijn Tori with two by two windows. J. Comb. Theory Ser. A 76(2), 213\u2013230 (1996)","journal-title":"J. Comb. Theory Ser. A"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-319-07566-2_21","volume-title":"Combinatorial Pattern Matching","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Computing k-th Lyndon word and decoding lexicographically minimal de Bruijn sequence. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 202\u2013211. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_21"},{"issue":"1","key":"26_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a007","volume":"12","author":"S Kopparty","year":"2016","unstructured":"Kopparty, S., Kumar, M., Saks, M.: Efficient indexing of necklaces and irreducible polynomials over finite fields. Theory Comput. 12(1), 1\u201327 (2016)","journal-title":"Theory Comput."},{"issue":"1","key":"26_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"JK Lanctot","year":"2003","unstructured":"Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inf. Comput. 185(1), 41\u201355 (2003)","journal-title":"Inf. Comput."},{"issue":"2","key":"26_CR26","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM 49(2), 157\u2013171 (2002)","journal-title":"J. ACM"},{"key":"26_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words. Cambridge Mathematical Library","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library, 2nd edn. Cambridge University Press, Cambridge (1997). https:\/\/doi.org\/10.1017\/CBO9780511566097","edition":"2"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Piskorski, J., Sydow, M., Wieloch, K.: Comparison of string distance metrics for lemmatisation of named entities in polish. In: Language and Technology Conference, pp. 413\u2013427 (2007)","DOI":"10.1007\/978-3-642-04235-5_36"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Recchia, G., Louwerse, M.M.: A comparison of string similarity measures for toponym matching. In: SIGSPATIAL 2013, pp. 54\u201361 (2013)","DOI":"10.1145\/2534848.2534850"},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Ruskey, F., Savage, C., Min Yih Wang, T.: Generating necklaces. J. Algorithms 13(3), 414\u2013430 (1992)","DOI":"10.1016\/0196-6774(92)90047-G"},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Ruskey, F., Sawada, J.: Generating Necklaces and Strings with Forbidden Substrings. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics, COCOON 2000. LNCS, vol 1858, pp. 330\u2013339. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44968-X_33","DOI":"10.1007\/3-540-44968-X_33"},{"key":"26_CR32","doi-asserted-by":"publisher","unstructured":"Siromoney, G., Siromoney, R., Robinson, T.: Kahbi kolam and cycle grammars, pp. 267\u2013300. Springer-Verlag (1987). https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/9789814368452_0017, https:\/\/doi.org\/10.1142\/9789814368452_0017","DOI":"10.1142\/9789814368452_0017"},{"key":"26_CR33","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Quick k-median, k-center, and facility location for sparse graphs. SIAM J. Comput. 34(2), 405\u2013432 (2005). http:\/\/arxiv.org\/abs\/https:\/\/doi.org\/10.1137\/S0097539701388884, https:\/\/doi.org\/10.1137\/S0097539701388884","DOI":"10.1137\/S0097539701388884"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2023: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-23101-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T18:55:36Z","timestamp":1728586536000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-23101-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031231001","9783031231018"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-23101-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nov\u00fd Smokovec","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 January 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 January 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ics.science.upjs.sk\/sofsem2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3+","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6-7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}