{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T16:30:44Z","timestamp":1775061044093,"version":"3.50.1"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032224682","type":"print"},{"value":"9783032224699","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-22469-9_7","type":"book-chapter","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:57:54Z","timestamp":1775055474000},"page":"114-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Computational Aspects of\u00a0Cores of\u00a0Ordered Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6880-4896","authenticated-orcid":false,"given":"Michal","family":"\u010cert\u00edk","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5133-5586","authenticated-orcid":false,"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Axenovich, M., Rollin, J., Ueckerdt, T.: Chromatic number of ordered graphs with forbidden ordered subgraphs. Combinatorica 38, 1021\u20131043 (2016). https:\/\/api.semanticscholar.org\/CorpusID:7776173","DOI":"10.1007\/s00493-017-3593-0"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Balko, M., Poljak, M.: On off-diagonal ordered ramsey numbers of nested matchings (2022)","DOI":"10.1007\/978-3-030-83823-2_38"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"208","DOI":"10.4153\/s0008414x2300086x","volume":"77","author":"P Bhowmik","year":"2023","unstructured":"Bhowmik, P., Iosevich, A., Koh, D., Pham, T.: Multi-linear forms, graphs, and LP -improving measures in BBB FQD. Can. J. Math. 77(1), 208\u2013251 (2023). https:\/\/doi.org\/10.4153\/s0008414x2300086x","journal-title":"Can. J. Math."},{"key":"7_CR4","unstructured":"Bodirsky, M.: Graph homomorphisms and universal algebra (2026). https:\/\/wwwpub.zih.tu-dresden.de\/~bodirsky\/GH-UA.pdf, course notes (draft)"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Giocanti, U., Ossona\u00a0de Mendez, P., Simon, P., Thomass\u00e9, S., Toru\u0144czyk, S.: Twin-width IV: ordered graphs and matrices. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) (2022). https:\/\/doi.org\/10.1145\/3519935.3520037","DOI":"10.1145\/3519935.3520037"},{"key":"7_CR6","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Ne\u0161et\u0159 il, J., Mendez, P.O., Siebertz, S., Thomass\u00e9, S.: Twin-width and permutations. In: European Conference on Combinatorics, Graph Theory and Applications, vol. 12, pp. 156\u2013162 (2023). https:\/\/doi.org\/10.5817\/cz.muni.eurocomb23-022","DOI":"10.5817\/cz.muni.eurocomb23-022"},{"key":"7_CR7","unstructured":"\u010cert\u00edk, M.: Homomorphisms of ordered graphs. Ph.D. thesis, Charles University, Prague (2025)"},{"key":"#cr-split#-7_CR8.1","doi-asserted-by":"crossref","unstructured":"\u010cert\u00edk, M., Feldmann, A.E., Ne\u0161et\u0159il, J., Rz\u0105\u017cewski, P.: Complexity aspects of homomorphisms of ordered graphs (2025). https:\/\/sofsem.uj.edu.pl\/papers.html, accepted","DOI":"10.1007\/978-3-032-17801-5_31"},{"key":"#cr-split#-7_CR8.2","unstructured":"to appear in SOFSEM 2026 - 51st International Conference on Current Trends in Theory and Practice of Computer Science. LNCS. Springer Nature Switzerland. https:\/\/arxiv.org\/abs\/2511.23078"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"\u010cert\u00edk, M., Feldmann, A.E., Ne\u0161et\u0159il, J., Rz\u0105\u017cewski, P.: On Computational aspects of ordered matching problems. In: Liu, Z., Saoud, A., Wehrheim, H. (eds.) Theoretical Aspects of Computing \u2013 ICTAC 2025, pp. 459\u2013467. Lecture Notes in Computer Science, Springer Nature Switzerland (2025). https:\/\/link.springer.com\/chapter\/10.1007\/978-3-032-11176-0_27, full version: http:\/\/arxiv.org\/abs\/2511.23093","DOI":"10.1007\/978-3-032-11176-0_27"},{"key":"7_CR10","unstructured":"\u010cert\u00edk, M., Ne\u0161et\u0159il, J.: Duality and $$\\chi ^<$$-Boundedness of ordered relational systems (2025). full version article in preparation"},{"key":"7_CR11","unstructured":"\u010cert\u00edk, M., Ne\u0161et\u0159il, J.: Duality, $$\\chi ^<$$-Boundedness and order density of ordered graphs. Commentationes Mathematicae Universitatis Carolinae (2026). https:\/\/arxiv.org\/abs\/2310.00852, accepted for publication"},{"issue":"8","key":"7_CR12","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Conlon, D., Fox, J., Lee, C., Sudakov, B.: Ordered ramsey numbers (2016)","DOI":"10.1016\/j.jctb.2016.06.007"},{"issue":"6","key":"7_CR14","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.1007\/s00493-024-00119-x","volume":"44","author":"R Connelly","year":"2024","unstructured":"Connelly, R., Gortler, S.J., Theran, L.: Reconstruction in one dimension from unlabeled Euclidean lengths. Combinatorica 44(6), 1325\u20131351 (2024). https:\/\/doi.org\/10.1007\/s00493-024-00119-x","journal-title":"Combinatorica"},{"key":"7_CR15","unstructured":"Cygan, M., et al.: Parameterized Algorithms, 1st edn. Springer Publishing Company, Incorporated (2015)"},{"issue":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976). https:\/\/doi.org\/10.1137\/0205048","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR17","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1137\/1024022","volume":"24","author":"MR Garey","year":"1982","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. SIAM Rev. 24(1), 90\u201391 (1982). https:\/\/doi.org\/10.1137\/1024022","journal-title":"SIAM Rev."},{"key":"7_CR18","doi-asserted-by":"publisher","unstructured":"Ge, Y., et al.: Can graph descriptive order affect solving graph problems with LLMs? arXiv (2024). https:\/\/doi.org\/10.48550\/arxiv.2402.07140","DOI":"10.48550\/arxiv.2402.07140"},{"key":"7_CR19","doi-asserted-by":"publisher","unstructured":"Goerttler, S., Wu, M., He, F.: Machine learning applications in medicine and biology. arXiv, pp. 1\u201341 (2024). https:\/\/doi.org\/10.1007\/978-3-031-51893-5_1","DOI":"10.1007\/978-3-031-51893-5_1"},{"key":"7_CR20","doi-asserted-by":"publisher","unstructured":"Grytczuk, J., Pawlik, B., Ruci\u0144ski, A.: Shuffle squares and nest-free graphs. arXiv (2025). https:\/\/doi.org\/10.48550\/arxiv.2503.22043","DOI":"10.48550\/arxiv.2503.22043"},{"key":"7_CR21","doi-asserted-by":"publisher","unstructured":"Guo, H., Song, X., Lindner, A.B.: Seq2DFUNC: 2-dimensional convolutional neural network on graph representation of synthetic sequences from massive-throughput assay. bioRxiv p. 2019.12.22.886085 (2019). https:\/\/doi.org\/10.1101\/2019.12.22.886085","DOI":"10.1101\/2019.12.22.886085"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Hedrl\u00edn, Z., Pultr, A., Trnkov\u00e1, V.: Concerning a categorial approach to topological and algebraic theories. In: General Topology and its Relations to Modern Analysis and Algebra, pp. 176\u2013181. Academia Publishing House of the Czechoslovak Academy of Sciences (1967). http:\/\/eudml.org\/doc\/220068","DOI":"10.1016\/B978-1-4831-9850-7.50047-3"},{"key":"7_CR23","doi-asserted-by":"publisher","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: The core of a graph. Discr. Math. 109(1), 117\u2013126 (1992). https:\/\/doi.org\/10.1016\/0012-365X(92)90282-K, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0012365X9290282K","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and homomorphisms. Oxford University Press (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"7_CR25","doi-asserted-by":"publisher","unstructured":"Kourani, H., Schuster, D., Aalst, W.V.D.: Scalable discovery of partially ordered workflow models with formal guarantees. In: 2023 5th International Conference on Process Mining (ICPM), 89\u201396 (2023). https:\/\/doi.org\/10.1109\/icpm60904.2023.10271941","DOI":"10.1109\/icpm60904.2023.10271941"},{"key":"7_CR26","doi-asserted-by":"publisher","unstructured":"Kourani, H., Zelst, S.: Business process management. Lecture Notes Comput. Sci., pp. 92\u2013108 (2023). https:\/\/doi.org\/10.1007\/978-3-031-41620-0_6","DOI":"10.1007\/978-3-031-41620-0_6"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Kun, G., Ne\u0161et\u0159il, J.: Dichotomy for orderings?, pp. 4175\u20134187 (2026). https:\/\/doi.org\/10.1137\/1.9781611978971.153, https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611978971.153, proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","DOI":"10.1137\/1.9781611978971.153"},{"key":"7_CR28","doi-asserted-by":"publisher","unstructured":"Li, X., Yao, P., Pan, Y.: Understanding complex systems. Understand. Complex Syst., pp. 341\u2013371 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47824-0_13","DOI":"10.1007\/978-3-662-47824-0_13"},{"key":"7_CR29","unstructured":"Lim, K., Shin, N.H., Young-Yoon, Kim, C.S.: Order learning and its application to age estimation. In: International Conference on Learning Representations (2020). https:\/\/openreview.net\/forum?id=HygsuaNFwr"},{"key":"7_CR30","doi-asserted-by":"publisher","unstructured":"Malkhi, D., Stathakopoulou, C., Yin, M.: BBCA-CHAIN: low latency, high throughput BFT consensus on a DAG. arXiv (2023). https:\/\/doi.org\/10.48550\/arxiv.2310.06335","DOI":"10.48550\/arxiv.2310.06335"},{"key":"7_CR31","unstructured":"Ne\u0161et\u0159il, J.: Ramsey Theory, pp. 1331\u20131403. MIT Press, Cambridge, MA, USA (1996)"},{"key":"7_CR32","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Towards a characterization of universal categories (2016)"},{"key":"7_CR33","doi-asserted-by":"publisher","unstructured":"Pach, J., Tardos, G.: Forbidden paths and cycles in ordered graphs and matrices. Israel J. Math. (2006). https:\/\/doi.org\/10.1007\/BF02773960","DOI":"10.1007\/BF02773960"},{"issue":"10","key":"7_CR34","doi-asserted-by":"publisher","first-page":"1838","DOI":"10.3390\/math8101838","volume":"8","author":"R Romansky","year":"2020","unstructured":"Romansky, R.: An approach for mathematical modeling and investigation of computer processes at a macro level. Mathematics 8(10), 1838 (2020). https:\/\/doi.org\/10.3390\/math8101838","journal-title":"Mathematics"},{"key":"7_CR35","doi-asserted-by":"publisher","unstructured":"Tardos, G.: Extremal theory of vertex or edge ordered graphs. In: Lo, A., Mycroft, R., Perarnau, G., Treglown, A. (eds.) Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Conference, Birmingham, UK, July 29 - August 2, 2019, pp. 221\u2013236. Cambridge University Press (2019). https:\/\/doi.org\/10.1017\/9781108649094.008","DOI":"10.1017\/9781108649094.008"},{"key":"7_CR36","doi-asserted-by":"publisher","unstructured":"Thomas, T., Surendran, R., John, T.S., Alazab, M.: Intelligent mobile malware detection, pp. 69\u201378 (2023). https:\/\/doi.org\/10.1201\/9781003121510-5","DOI":"10.1201\/9781003121510-5"},{"issue":"1","key":"7_CR37","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1525\/1\/012017","volume":"1525","author":"A Verbytskyi","year":"2020","unstructured":"Verbytskyi, A., et al.: HepMC3 event record library for monte carlo event generators. J. Phys: Conf. Ser. 1525(1), 012017 (2020). https:\/\/doi.org\/10.1088\/1742-6596\/1525\/1\/012017","journal-title":"J. Phys: Conf. Ser."},{"key":"7_CR38","doi-asserted-by":"publisher","first-page":"93464","DOI":"10.1109\/access.2022.3172684","volume":"10","author":"D Wang","year":"2022","unstructured":"Wang, D., Tian, F., Wei, D.: An improved ordered visibility graph aggregation operator for MADM. IEEE Access 10, 93464\u201393474 (2022). https:\/\/doi.org\/10.1109\/access.2022.3172684","journal-title":"IEEE Access"},{"key":"7_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2025.127767","volume":"285","author":"Z Xing","year":"2025","unstructured":"Xing, Z., Zhao, W.: Block-diagonal structure learning for subspace clustering. Expert Syst. Appl. 285, 127767 (2025). https:\/\/doi.org\/10.1016\/j.eswa.2025.127767","journal-title":"Expert Syst. Appl."}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22469-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:57:56Z","timestamp":1775055476000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22469-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032224682","9783032224699"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22469-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RAMICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"B\u0119dlewo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}