{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:30:59Z","timestamp":1775097059981,"version":"3.50.1"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","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-17801-5_31","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:34Z","timestamp":1770918814000},"page":"416-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity Aspects of\u00a0Homomorphisms 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,2,13]]},"reference":[{"key":"31_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":"31_CR2","doi-asserted-by":"publisher","unstructured":"Balko, M., Cibulka, J., Kr\u00e1l, K., Kyn\u010dl, J.: Ramsey numbers of ordered graphs. Electron. J. Comb. 27(1) (2020). https:\/\/doi.org\/10.37236\/7816, http:\/\/dx.doi.org\/10.37236\/7816","DOI":"10.37236\/7816"},{"key":"31_CR3","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"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.jctb.2022.02.006","volume":"155","author":"J Balogh","year":"2022","unstructured":"Balogh, J., Li, L., Treglown, A.: Tilings in vertex ordered graphs. J. Comb. Theory, Ser. B 155, 171\u2013201 (2022). https:\/\/doi.org\/10.1016\/j.jctb.2022.02.006","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"31_CR5","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":"31_CR6","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Giocanti, U., de\u00a0Mendez, P.O., Simon, P., Thomass\u00e9, S., Toru\u0144czyk, S.: Twin-width iv: ordered graphs and matrices (2021)","DOI":"10.1145\/3519935.3520037"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O., Siebertz, S., Thomass\u00e9, S.: Twin-width and permutations (2024)","DOI":"10.46298\/lmcs-20(3:4)2024"},{"issue":"8","key":"31_CR8","doi-asserted-by":"publisher","first-page":"2360","DOI":"10.1007\/s00453-020-00730-6","volume":"82","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in h-free graphs. Algorithmica 82(8), 2360\u20132394 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00730-6","journal-title":"Algorithmica"},{"issue":"1","key":"31_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Comput. Geom. 28(1), 11\u201318 (2004). https:\/\/doi.org\/10.1016\/j.comgeo.2004.01.003","journal-title":"Comput. Geom."},{"key":"31_CR10","doi-asserted-by":"publisher","unstructured":"Brandenburg, F.J.: Graph-grammars and their application to computer science. In: 3rd International Workshop Warrenton, Virginia, USA, 2\u20136 December 1986. LNCS, pp. 99\u2013111 (2005). https:\/\/doi.org\/10.1007\/3-540-18771-5_48","DOI":"10.1007\/3-540-18771-5_48"},{"issue":"1","key":"31_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s11856-012-0149-2","volume":"196","author":"B Braun","year":"2013","unstructured":"Braun, B., Browder, J., Klee, S.: Cellular resolutions of ideals defined by nondegenerate simplicial homomorphisms. Israel J. Math. 196(1), 321\u2013344 (2013). https:\/\/doi.org\/10.1007\/s11856-012-0149-2","journal-title":"Israel J. Math."},{"key":"31_CR12","unstructured":"\u010cert\u00edk, M.: Homomorphisms of Ordered Graphs. Ph.D. thesis, Charles University, Prague (2025), PhD thesis, in preparation"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"\u010cert\u00edk, M., Feldmann, A.E., Ne\u0161et\u0159il, J., Rz\u0105\u017cewski, P.: On computational aspects of ordered matchings (2025). http:\/\/arxiv.org\/abs\/2511.23093","DOI":"10.1007\/978-3-032-11176-0_27"},{"key":"31_CR14","unstructured":"\u010cert\u00edk, M., Ne\u0161et\u0159il, J.: Duality, $$\\chi ^{<}$$-boundedness and order density of ordered graphs (2023). https:\/\/arxiv.org\/abs\/2310.00852"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"\u010cert\u00edk, M., Feldmann, A.E., Ne\u0161et\u0159il, J., Rz\u0105\u017cewski, P.: On computational aspects of cores of ordered graphs (2025). http:\/\/arxiv.org\/abs\/2511.23099","DOI":"10.1007\/978-3-032-11176-0_27"},{"key":"31_CR16","unstructured":"\u010cert\u00edk, M., Feldmann, A.E., Ne\u0161et\u0159il, J., Rz\u0105\u017cewski, P.: Complexity aspects of homomorphisms of ordered graphs (2025). https:\/\/arxiv.org\/abs\/2511.23078"},{"key":"31_CR17","doi-asserted-by":"publisher","unstructured":"Chen, J., Liu, Y., Liu, X., Peng, S.: PGS-BFT: a pipeline-based graph structure byzantine fault tolerance consensus algorithm. In: 2023 3rd International Conference on Computer Science and Blockchain (CCSB), vol. 00, pp. 133\u2013138 (2023). https:\/\/doi.org\/10.1109\/ccsb60789.2023.10398859","DOI":"10.1109\/ccsb60789.2023.10398859"},{"key":"31_CR18","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":"31_CR19","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":"31_CR20","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Tight bounds for graph homomorphism and subgraph isomorphism, pp. 1643\u20131649. https:\/\/doi.org\/10.1137\/1.9781611974331.ch112, https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611974331.ch112","DOI":"10.1137\/1.9781611974331.ch112"},{"key":"31_CR21","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized algorithms, pp. 285\u2013319 (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3_9","DOI":"10.1007\/978-3-319-21275-3_9"},{"issue":"3","key":"31_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/rsa.3240070304","volume":"7","author":"D Duffus","year":"1995","unstructured":"Duffus, D., Ginn, M., R\u00f6dl, V.: On the computational complexity of ordered subgraph recognition. Random Struct. Algorithms 7(3), 223\u2013268 (1995). https:\/\/doi.org\/10.1002\/rsa.3240070304","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"31_CR23","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1007\/s00453-022-01052-5","volume":"85","author":"P Dvo\u0159\u00e1k","year":"2023","unstructured":"Dvo\u0159\u00e1k, P., Feldmann, A.E., Rai, A., Rz\u0105\u017cewski, P.: Parameterized inapproximability of independent set in h-free graphs. Algorithmica 85(4), 902\u2013928 (2023). https:\/\/doi.org\/10.1007\/s00453-022-01052-5","journal-title":"Algorithmica"},{"key":"31_CR24","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":"31_CR25","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":"31_CR26","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"},{"issue":"1","key":"31_CR27","doi-asserted-by":"publisher","first-page":"67","DOI":"10.2140\/involve.2012.5.67","volume":"5","author":"L Guerra","year":"2012","unstructured":"Guerra, L., Klee, S.: Betti numbers of order-preserving graph homomorphisms. Involve, J. Math. 5(1), 67\u201380 (2012)","journal-title":"Involve, J. Math."},{"key":"31_CR28","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":"31_CR29","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":"31_CR30","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1986","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of $$h$$-coloring. J. Comb. Theory 48, 92\u2013110 (1986)","journal-title":"J. Comb. Theory"},{"key":"31_CR31","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":"31_CR32","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), vol. 00, pp. 89\u201396 (2023). https:\/\/doi.org\/10.1109\/icpm60904.2023.10271941","DOI":"10.1109\/icpm60904.2023.10271941"},{"key":"31_CR33","doi-asserted-by":"publisher","unstructured":"Kourani, H., Zelst, S.J.V.: Business process management. Lecture Notes in Computer Science, 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":"31_CR34","doi-asserted-by":"publisher","unstructured":"Kun, G., Ne\u0161et\u0159il, J.: Dichotomy for orderings? arXiv (2025). https:\/\/doi.org\/10.48550\/arxiv.2504.13268","DOI":"10.48550\/arxiv.2504.13268"},{"key":"31_CR35","doi-asserted-by":"publisher","unstructured":"Kuzmina, E.A., Nizamova, G.F.: Curriculum development based on the graph model. Inf. Educ. (5), 33\u201343 (2020). https:\/\/doi.org\/10.32517\/0234-0453-2020-35-5-33-43","DOI":"10.32517\/0234-0453-2020-35-5-33-43"},{"key":"31_CR36","doi-asserted-by":"publisher","unstructured":"Li, X., Yao, P., Pan, Y.: Understanding complex systems. Underst. Complex Syst. 341\u2013371 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47824-0_13","DOI":"10.1007\/978-3-662-47824-0_13"},{"key":"31_CR37","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":"31_CR38","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":"31_CR39","unstructured":"Ne\u0161et\u0159il, J.: Ramsey Theory, pp. 1331\u20131403. MIT Press, Cambridge, MA, USA (1996)"},{"key":"31_CR40","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Towards a characterization of universal categories (2016)"},{"issue":"4","key":"31_CR41","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1002\/jgt.23002","volume":"104","author":"J Nie","year":"2023","unstructured":"Nie, J., Surya, E., Zeng, J.: On asymptotic packing of convex geometric and ordered graphs. J. Graph Theory 104(4), 836\u2013850 (2023). https:\/\/doi.org\/10.1002\/jgt.23002","journal-title":"J. Graph Theory"},{"key":"31_CR42","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, https:\/\/doi.org\/10.1007\/BF02773960","DOI":"10.1007\/BF02773960"},{"issue":"10","key":"31_CR43","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":"31_CR44","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":"31_CR45","doi-asserted-by":"publisher","first-page":"012017","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":"31_CR46","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":"31_CR47","doi-asserted-by":"publisher","first-page":"127767","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."},{"issue":"OOPSLA2","key":"31_CR48","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1145\/3622842","volume":"7","author":"Q Zhang","year":"2023","unstructured":"Zhang, Q., et al.: Building dynamic system call sandbox with partial order analysis. Proc. ACM Program. Lang. 7(OOPSLA2), 1253\u20131280 (2023). https:\/\/doi.org\/10.1145\/3622842","journal-title":"Proc. ACM Program. Lang."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:37Z","timestamp":1770918817000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_31","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":"13 February 2026","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":"Krakow","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":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}