{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:23:52Z","timestamp":1764059032903,"version":"3.45.0"},"reference-count":27,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T00:00:00Z","timestamp":1761436800000},"content-version":"vor","delay-in-days":298,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Procedia Computer Science"],"published-print":{"date-parts":[[2025]]},"DOI":"10.1016\/j.procs.2025.10.324","type":"journal-article","created":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:19:08Z","timestamp":1764058748000},"page":"397-404","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Finding subdigraphs in digraphs of bounded directed treewidth"],"prefix":"10.1016","volume":"273","author":[{"given":"Raul","family":"Lopes","sequence":"first","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.procs.2025.10.324_bib1","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Bessy, S., Jackson, B., Kriesell, M., 2017. Antistrong digraphs. Journal of Combinatorial Theory, Series B 122, 68-90. doi: 10.1016\/j.jctb.2016.05.004.","DOI":"10.1016\/j.jctb.2016.05.004"},{"key":"10.1016\/j.procs.2025.10.324_bib2","unstructured":"Berman, P., Karpinski, M, Scott, A.D., 2003. Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium on Computational Complexity (ECCC) TR03-022. URL: https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2003\/TR03-022\/index.html."},{"key":"10.1016\/j.procs.2025.10.324_bib3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, 1305-1317. doi: 10.1137\/S0097539793251219.","DOI":"10.1137\/S0097539793251219"},{"key":"10.1016\/j.procs.2025.10.324_bib4","series-title":"Graph Theory","author":"Bondy","year":"2008"},{"key":"10.1016\/j.procs.2025.10.324_bib5","doi-asserted-by":"crossref","unstructured":"Campos, V., Lopes, R., Maia, A.K., Sau, I., 2022. Adapting the directed grid theorem into an fpt algorithm. SIAM Journal on Discrete Mathematics 36, 1887-1917. doi: 10.1137\/21M1452664.","DOI":"10.1137\/21M1452664"},{"key":"10.1016\/j.procs.2025.10.324_bib6","doi-asserted-by":"crossref","unstructured":"Courcelle, B., 1990. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation 85, 12-75. doi: 10.1016\/0890-5401(90)90043-H.","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"10.1016\/j.procs.2025.10.324_bib7","series-title":"Parameterized Algorithms","author":"Cygan","year":"2015"},{"key":"10.1016\/j.procs.2025.10.324_bib8","series-title":"Fundamentals of Parameterized Complexity","author":"Downey","year":"2013"},{"key":"10.1016\/j.procs.2025.10.324_bib9","doi-asserted-by":"crossref","unstructured":"Ganian, R., Hlinen\u00fd, P., Kneis, J., Meister, D., Obdrz\u00e1lek, J., Rossmanith, P., Sikdar, S., 2016. Are there any good digraph width measures? Journal of Combinatorial Theory, Series B 116, 250-286. doi: 10.1016\/J.JCTB.2015.09.001.","DOI":"10.1016\/j.jctb.2015.09.001"},{"key":"10.1016\/j.procs.2025.10.324_bib10","doi-asserted-by":"crossref","unstructured":"Giannopoulou, A.C., Kawarabayashi, K., Kreutzer, S., Kwon, O., 2020. The Directed Flat Wall Theorem, in: Proc. of the 13st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 239-258. doi: 10.1137\/1.9781611975994.15.","DOI":"10.1137\/1.9781611975994.15"},{"key":"10.1016\/j.procs.2025.10.324_bib11","doi-asserted-by":"crossref","unstructured":"Hatzel, M, Kreutzer, S., Milani, M.G., Muzi, I., 2024. Cycles of well-linked sets and an elementary bound for the directed grid theorem, in:Proc. of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1-20. doi: 10.1109\/F0CS61266.2024.00011.","DOI":"10.1109\/FOCS61266.2024.00011"},{"key":"10.1016\/j.procs.2025.10.324_bib12","doi-asserted-by":"crossref","unstructured":"Johnson, T, Robertson, N., Seymour, P.D., Thomas, R., 2001. Directed tree-width. Journal of Combinatorial Theory, Series B 82, 138-154. doi: 10.1006\/jctb.2000.2031.","DOI":"10.1006\/jctb.2000.2031"},{"key":"10.1016\/j.procs.2025.10.324_bib13","doi-asserted-by":"crossref","unstructured":"Jr., H.W.L., 1983. Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 538-548. doi: 10.1287\/MOOR.8.4.538.","DOI":"10.1287\/moor.8.4.538"},{"key":"10.1016\/j.procs.2025.10.324_bib14","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kreutzer, S., 2015. Towards the Graph Minor Theorems for Directed Graphs, in: Proc. of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 3-10. doi: 10.1007\/978-3-662-47666-6\\_1.","DOI":"10.1007\/978-3-662-47666-6_1"},{"key":"10.1016\/j.procs.2025.10.324_bib15","doi-asserted-by":"crossref","unstructured":"Korhonen, T, Lokshtanov, D., 2023. An improved parameterized algorithm for treewidth, in: Proc. of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 528-541. doi: 10.1145\/3564246.3585245.","DOI":"10.1145\/3564246.3585245"},{"key":"10.1016\/j.procs.2025.10.324_bib16","doi-asserted-by":"crossref","unstructured":"Lampis, M., Kaouri, G., Mtsou, V., 2011. On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization 8, 129-138. doi: 10.1016\/J.DIS0PT.2010.03.010.","DOI":"10.1016\/j.disopt.2010.03.010"},{"key":"10.1016\/j.procs.2025.10.324_bib17","doi-asserted-by":"crossref","unstructured":"Lopes, R., Sau, I., 2022. A relaxation of the directed disjoint paths problem: A global congestion metric helps. Theoretical Computer Science 898, 75-91. doi: 10.1016\/J.TCS.2021.10.023.","DOI":"10.1016\/j.tcs.2021.10.023"},{"key":"10.1016\/j.procs.2025.10.324_bib18","unstructured":"Maalouly, N.E., 2023. Exact Matching: Algorithms and Related Problems, in: Proc. of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 29:1-29:17. doi: 10.4230\/LIPICS.STACS.2023.29."},{"key":"10.1016\/j.procs.2025.10.324_bib19","unstructured":"Maalouly, N.E., 2024. Towards a Deterministic Polynomial Time Algorithm for the Exact Matching Problem. Ph.D. thesis. ETH Zurich, Z\u00fcrich, Switzerland. doi: 10.3929\/ETHZ-B-000675444."},{"key":"10.1016\/j.procs.2025.10.324_bib20","unstructured":"Maalouly, N.E., Haslebacher, S., Wulf, L., 2024. On the exact matching problem in dense graphs, in: Proc. of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 33:1-33:17. doi: 10.4230\/LIPICS.STACS.2024.33."},{"key":"10.1016\/j.procs.2025.10.324_bib21","unstructured":"Marx, D., Pilipczuk, M., 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask), in: Proc. of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 542-553. doi: 10.4230\/LIPICS.STACS.2014.542."},{"key":"10.1016\/j.procs.2025.10.324_bib22","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V., 1987. Matching is as easy as matrix inversion. Combinatorica 7, 105-113. doi: 10.1007\/BF02579206.","DOI":"10.1007\/BF02579206"},{"key":"10.1016\/j.procs.2025.10.324_bib23","doi-asserted-by":"crossref","unstructured":"de Oliveira Oliveira, M., 2016. An algorithmic metatheorem for directed treewidth. Discrete Applied Mathematics 204, 49-76. doi: 10.1016\/j.dam.2015.10.020.","DOI":"10.1016\/j.dam.2015.10.020"},{"key":"10.1016\/j.procs.2025.10.324_bib24","doi-asserted-by":"crossref","unstructured":"Plaisted, D.A., Zaks, S., 1980. An NP-complete matching problem. Discrete Applied Mathematics 2, 65-72. doi: 10.1016\/0166-218X(80)90055-4.","DOI":"10.1016\/0166-218X(80)90055-4"},{"key":"10.1016\/j.procs.2025.10.324_bib25","doi-asserted-by":"crossref","unstructured":"Reed, B.A., 1999. Introducing directed tree width. Electronic Notes in Discrete Mathematics 3, 222-229. doi: 10.1016\/S1571-0653C05)80061-7.","DOI":"10.1016\/S1571-0653(05)80061-7"},{"key":"10.1016\/j.procs.2025.10.324_bib26","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D., 1990. Graph minors. IV. tree-width and well-quasi-ordering. Journal of Combinatorial Theory, Series B 48, 227-254. doi: 10.1016\/0095-8956(90)90120-0.","DOI":"10.1016\/0095-8956(90)90120-O"},{"key":"10.1016\/j.procs.2025.10.324_bib27","doi-asserted-by":"crossref","unstructured":"Slivkins, A., 2010. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM Journal on Discrete Mathematics 24, 146-157. doi: 10.1137\/070697781.","DOI":"10.1137\/070697781"}],"container-title":["Procedia Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1877050925036713?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1877050925036713?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:19:38Z","timestamp":1764058778000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1877050925036713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":27,"alternative-id":["S1877050925036713"],"URL":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.324","relation":{},"ISSN":["1877-0509"],"issn-type":[{"value":"1877-0509","type":"print"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Finding subdigraphs in digraphs of bounded directed treewidth","name":"articletitle","label":"Article Title"},{"value":"Procedia Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.324","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}