{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T15:18:26Z","timestamp":1725981506371},"publisher-location":"Cham","reference-count":102,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319718392"},{"type":"electronic","value":"9783319718408"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-71840-8_9","type":"book-chapter","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T20:19:25Z","timestamp":1529353165000},"page":"405-466","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Digraphs of Bounded Width"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Kreutzer","sequence":"first","affiliation":[]},{"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,19]]},"reference":[{"issue":"5","key":"9_CR1","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.jctb.2006.12.006","volume":"97","author":"I Adler","year":"2007","unstructured":"I.\u00a0Adler. Directed tree-width examples. J. Combin. Theory Ser. B, 97(5):718\u2013725, 2007.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR2","first-page":"5","volume":"59","author":"B Alspach","year":"2006","unstructured":"B.\u00a0Alspach. Searching and sweeping graphs: a brief survey. Matematiche (Catania), 59:5\u201337, 2006.","journal-title":"Matematiche (Catania)"},{"key":"9_CR3","unstructured":"S.\u00a0Amiri, L.\u00a0Kaiser, S.\u00a0Kreutzer, R.\u00a0Rabinovich, and S.\u00a0Siebertz. Graph searching games and width measures for directed graphs. In STACS 2015: 32nd International Symposium on Theoretical Aspects of Computer Science, volume\u00a030 of LIPIcs, pages 34\u201347, 2015."},{"key":"9_CR4","unstructured":"S.\u00a0Amiri, K.\u00a0Kawarabayashi, S.\u00a0Kreutzer, and P.\u00a0Wollan. The Erd\u0151s-Posa property for directed graphs. CoRR, arXiv:1603.02504 , 2016."},{"issue":"2","key":"9_CR5","first-page":"277","volume":"8","author":"S Arnborg","year":"1987","unstructured":"S.\u00a0Arnborg, D.\u00a0Corneil, and A.\u00a0Proskurowski. Complexity of finding embeddings in a $$k$$-tree. SIAM J. Matrix Analysis Applications, 8(2):277\u2013284, 1987.","journal-title":"SIAM J. Matrix Analysis Applications"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"G.\u00a0Bagan, A.\u00a0Bonifati, and B.\u00a0Groz. A trichotomy for regular simple path queries on graphs. In PODS 2013: 32nd Symposium on Principles of Database Systems, pages 261\u2013272, New York, NY, USA, 2013. ACM.","DOI":"10.1145\/2463664.2467795"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1002\/jgt.21894","volume":"82","author":"J Bang-Jensen","year":"2016","unstructured":"J.\u00a0Bang-Jensen and T.M. Larsen. DAG-width and circumference of digraphs. J. Graph Theory, 82:194\u2013206, 2016.","journal-title":"J. Graph Theory"},{"issue":"2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J Bar\u00e1t","year":"2006","unstructured":"J.\u00a0Bar\u00e1t. Directed path-width and monotonicity in digraph searching. Graphs Combin., 22(2):161\u2013172, 2006.","journal-title":"Graphs Combin."},{"issue":"2","key":"9_CR9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1556\/SScMath.49.2012.2.1200","volume":"49","author":"J Barat","year":"2012","unstructured":"J.\u00a0Barat, P.\u00a0Hajnal, Y.\u00a0Lin, and A.\u00a0Yang. On the structure of graphs with path-width at most two. Studia Scientiarum Mathematicarum Hungarica, 49(2):211\u2013222, 2012.","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"B.\u00a0Bergougnoux, M.M. Kant\u00e9, and O.\u00a0Kwon. An optimal XP algorithm for hamiltonian cycle on graphs of bounded clique-width. In WADS 2017: 15th International Symposium on Algorithms and Data Structures, volume 10389 of Lect. Notes Comput. Sci., pages 121\u2013132, 2017.","DOI":"10.1007\/978-3-319-62127-2_11"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"D.\u00a0Berwanger, A.\u00a0Dawar, P.\u00a0Hunter, and S.\u00a0Kreutzer. DAG-width and parity games. In STACS 2006: Symp. on Theoretical Aspects of Computer Science, volume 3884 of Lect. Notes Comput. Sci., pages 524\u2013536. Springer, 2006.","DOI":"10.1007\/11672142_43"},{"issue":"4","key":"9_CR12","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.jctb.2012.04.004","volume":"102","author":"D Berwanger","year":"2012","unstructured":"D.\u00a0Berwanger, A.\u00a0Dawar, P.\u00a0Hunter, S.\u00a0Kreutzer, and J.\u00a0Obr\u017e\u00e1lek. DAG-width and parity games. J. Combin. Theory Ser. B, 102(4):900\u2013923, 2012.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"Dietmar Berwanger","year":"2005","unstructured":"D.\u00a0Berwanger and E.\u00a0Gr\u00e4del. Entanglement \u2013 a measure for the complexity of directed graphs with applications to logic and games. In LPAR 2005: Logic for Programming, Artificial Intelligence, and Reasoning, Lect. Notes Artif. Intel., pages 209\u2013223, 2005."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.07.010","volume":"463","author":"D Berwanger","year":"2012","unstructured":"D.\u00a0Berwanger, E.\u00a0Gr\u00e4del, L.\u00a0Kaiser, and R.\u00a0Rabinovich. Entanglement and the complexity of directed graphs. Theor. Comput. Sci., 463:2\u201325, 2012.","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9_CR15","first-page":"239","volume":"12","author":"D Bienstock","year":"1991","unstructured":"D.\u00a0Bienstock and P.D. Seymour. Monotonicity in graph searching. J. Algor., 12(2):239\u2013245, 1991.","journal-title":"Monotonicity in graph searching. J. Algor."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bouchet. Connectivity of isotropic systems. In Combinatorial Mathematics: 3rd International Conference (New York, 1985), volume 555 of Ann. New York Acad. Sci., pages 81\u201393, New York, 1989. New York Acad. Sci.","DOI":"10.1111\/j.1749-6632.1989.tb22439.x"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0095-8956(88)90055-X","volume":"45","author":"A Bouchet","year":"1988","unstructured":"A.\u00a0Bouchet. Graphic presentations of isotropic systems. J. Combin. Theory Ser. B, 45(1):58\u201376, 1988.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"9_CR18","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0195-6698(87)80027-6","volume":"8","author":"A Bouchet","year":"1987","unstructured":"A.\u00a0Bouchet. Isotropic systems. European J. Combin., 8(3):231\u2013244, 1987.","journal-title":"European J. Combin."},{"issue":"3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A Bouchet","year":"1987","unstructured":"A.\u00a0Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica, 7(3):243\u2013254, 1987.","journal-title":"Combinatorica"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.aim.2014.11.011","volume":"270","author":"M Chudnovsky","year":"2015","unstructured":"M.\u00a0Chudnovsky, A.\u00a0Scott, and P.D. Seymour. Disjoint paths in tournaments. Adv. Math., 270:582\u2013597, 2015.","journal-title":"Adv. Math."},{"issue":"6","key":"9_CR21","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1016\/j.dam.2011.03.020","volume":"160","author":"DG Corneil","year":"2012","unstructured":"D.G. Corneil, M.\u00a0Habib, J.\u00a0Lanlignel, B.\u00a0Reed, and U.\u00a0Rotics. Polynomial-time recognition of clique-width $$\\le 3$$ graphs. Discrete Appl. Math., 160(6):834\u2013865, 2012.","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"D.G. Corneil, H.\u00a0Lerchs, and L.S. Burlingham. Complement reducible graphs. Discrete Appl. Math., 3(3):163\u2013174, 1981.","journal-title":"Discrete Appl. Math."},{"key":"9_CR23","first-page":"193","volume-title":"Formal Models and Semantics","author":"Bruno COURCELLE","year":"1990","unstructured":"B.\u00a0Courcelle. Graph rewriting: An algebraic and logic approach. In J.\u00a0van Leeuwen, editor, Handbook of Theoretical Computer Science, volume\u00a02, pages 194 \u2013 242. Elsevier, 1990."},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"B.\u00a0Courcelle and J.\u00a0Engelfriet. Graph structure and monadic second-order logic. Cambridge Univ. Press, Cambridge, 2012. A language-theoretic approach, With a foreword by M. Nivat.","DOI":"10.1017\/CBO9780511977619"},{"issue":"2","key":"9_CR25","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"B.\u00a0Courcelle, J.\u00a0Engelfriet, and G.\u00a0Rozenberg. Handle-rewriting hypergraph grammars. J. Comput. System Sci., 46(2):218\u2013270, 1993.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"9_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"B.\u00a0Courcelle, J.A. Makowsky, and U.\u00a0Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125\u2013150, 2000.","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9_CR27","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B Courcelle","year":"2007","unstructured":"B.\u00a0Courcelle and S.\u00a0Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Combin. Theory Ser. B, 97(1):91\u2013126, 2007.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"9_CR28","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"W.H. Cunningham. Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods, 3(2):214\u2013228, 1982.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.dam.2015.10.020","volume":"204","author":"M Oliveira de","year":"2016","unstructured":"M.\u00a0de\u00a0Oliveira\u00a0Oliveira. An algorithmic metatheorem for directed treewidth. Discrete Appl. Math., 204:49\u201376, 2016.","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9_CR30","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Z.\u00a0Dvo\u0159\u00e1k. Constant-factor approximation of the domination number in sparse graphs. European J. Combin., 34(5):833\u2013840, 2013.","journal-title":"European J. Combin."},{"key":"9_CR31","unstructured":"K.\u00a0Edwards, I.\u00a0Muzi, and P.\u00a0Wollan. Half-integral linkages in highly connected directed graphs. CoRR, arXiv:1611.01004 , 2016."},{"key":"9_CR32","doi-asserted-by":"crossref","unstructured":"W.\u00a0Espelage, F.\u00a0Gurski, and E.\u00a0Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In WG 2001: Graph-theoretic concepts in computer science, volume 2204 of Lect. Notes Comput. Sci., pages 117\u2013128. Springer, Berlin, 2001.","DOI":"10.1007\/3-540-45477-2_12"},{"key":"9_CR33","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.dam.2013.05.005","volume":"168","author":"H Fernau","year":"2014","unstructured":"H.\u00a0Fernau and D.\u00a0Meister. Digraphs of bounded elimination width. Discrete Appl. Math., 168:78\u201387, 2014.","journal-title":"Discrete Appl. Math."},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"J.\u00a0Flum and M.\u00a0Grohe. Parameterized Complexity Theory. Springer, 2006. ISBN 3-54-029952-1.","DOI":"10.2168\/LMCS-1(1:2)2005"},{"issue":"5","key":"9_CR35","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"F.V. Fomin, P.A. Golovach, D.\u00a0Lokshtanov, and S.\u00a0Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput., 43(5):1541\u20131563, 2014.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9_CR36","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"F.V. Fomin, P.A. Golovach, D.\u00a0Lokshtanov, and S.\u00a0Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941\u20131956, 2010.","journal-title":"SIAM J. Comput."},{"key":"9_CR37","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1137\/1.9781611973105.29","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Fedor V. Fomin","year":"2013","unstructured":"F.V. Fomin and M.\u00a0Pilipczuk. Jungles, bundles and fixed-parameter tractability. In SODA 2013: 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 396\u2013413, 2013."},{"issue":"3","key":"9_CR38","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"FV Fomin","year":"2008","unstructured":"F.V. Fomin and D.M. Thilikos. An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci., 399(3):236\u2013245, 2008.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR39","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"S.\u00a0Fortune, J.E. Hopcroft, and J.\u00a0Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111\u2013121, 1980.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR40","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jctb.2014.07.002","volume":"110","author":"A Fradkin","year":"2015","unstructured":"A.\u00a0Fradkin and P.D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. J. Combin. Theory Ser. B, 110:19\u201346, 2015.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR41","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.dam.2013.10.038","volume":"168","author":"R Ganian","year":"2014","unstructured":"R.\u00a0Ganian, P.\u00a0Hlin\u011bn\u00fd, J.\u00a0Kneis, A.\u00a0Langer, J.\u00a0Obdr\u017e\u00e1lek, and P.\u00a0Rossmanith. Digraph width measures in parameterized algorithmics. Discrete Appl. Math., 168:88\u2013107, 2014.","journal-title":"Discrete Appl. Math."},{"key":"9_CR42","doi-asserted-by":"crossref","unstructured":"R.\u00a0Ganian, P.\u00a0Hlin\u011bn\u00fd, J.\u00a0Kneis, A.\u00a0Langer, J.\u00a0Obdr\u017e\u00e1lek, and P.\u00a0Rossmanith. On digraph width measures in parameterized algorithmics. In IWPEC 2009: Parameterized and Exact Computation, volume 5917 of Lect. Notes Comput. Sci., pages 185\u2013197. Springer, Berlin, 2009.","DOI":"10.1007\/978-3-642-11269-0_15"},{"key":"9_CR43","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.jctb.2015.09.001","volume":"116","author":"R Ganian","year":"2016","unstructured":"R.\u00a0Ganian, P.\u00a0Hlin\u011bn\u00fd, J.\u00a0Kneis, D. Meister, J.\u00a0Obdr\u017e\u00e1lek, P.\u00a0Rossmanith, and S.\u00a0Sikdar. Are there any good digraph width measures? J. Combin. Theory Ser. B, 116:250\u2013286, 2016.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"9_CR44","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1016\/j.ejc.2012.07.024","volume":"34","author":"R Ganian","year":"2013","unstructured":"R.\u00a0Ganian, P.\u00a0Hlin\u011bn\u00fd, and J.\u00a0Obdr\u017e\u00e1lek. A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width. European J. Combin., 34(3):680\u2013701, 2013.","journal-title":"European J. Combin."},{"issue":"1","key":"9_CR45","first-page":"59","volume":"123","author":"R Ganian","year":"2013","unstructured":"R.\u00a0Ganian, P.\u00a0Hlin\u011bn\u00fd, and J.\u00a0Obdr\u017e\u00e1lek. Better algorithms for satisfiability problems for formulas of bounded rank-width. Fund. Inform., 123(1):59\u201376, 2013.","journal-title":"Fund. Inform."},{"key":"9_CR46","doi-asserted-by":"crossref","unstructured":"M.\u00a0Grohe, S.\u00a0Kreutzer, and S.\u00a0Siebertz. Deciding first-order properties of nowhere dense graphs. In STOC 2014: 46th Annual ACM Symposium on Theory of Computing, pages 89\u201398. ACM, 2014.","DOI":"10.1145\/2591796.2591851"},{"key":"9_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2015.11.003","volume":"616","author":"F Gurski","year":"2016","unstructured":"F.\u00a0Gurski, E.\u00a0Wanke, and E.\u00a0Yilmaz. Directed NLC-width. Theor. Comput. Sci., 616:1\u201317, 2016.","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9_CR48","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1137\/S0097539702418589","volume":"35","author":"Petr Hlinen\u00fd","year":"2005","unstructured":"P.\u00a0Hlin\u011bn\u00fd. A parametrized algorithm for matroid branch-width. SIAM J. Comput., 35(2):259\u2013277, loose erratum, 2005.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"9_CR49","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlin\u011bn\u00fd","year":"2008","unstructured":"P.\u00a0Hlin\u011bn\u00fd and S.\u00a0Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput., 38(3):1012\u20131032, 2008.","journal-title":"SIAM J. Comput."},{"key":"9_CR50","unstructured":"P.\u00a0Hunter. Losing the +1: Directed path-width games are monotone. Unpublished note, available from Feb. 2017 at www.cs.ox.ac.uk\/paul.hunter\/papers\/losing.pdf , 2006."},{"issue":"3","key":"9_CR51","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P Hunter","year":"2008","unstructured":"P.\u00a0Hunter and S.\u00a0Kreutzer. Digraph measures: Kelly decompositions, games, and ordering. Theor. Comput. Sci., 399(3):206\u2013219, 2008.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR52","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"S.\u00a0Iwata, L.\u00a0Fleischer, and S.\u00a0Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. Assoc. Comput. Mach., 48:761\u2013777, 2001.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"7","key":"9_CR53","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.dam.2009.02.007","volume":"158","author":"V Jel\u00ednek","year":"2010","unstructured":"V.\u00a0Jel\u00ednek. The rank-width of the square grid. Discrete Appl. Math., 158(7):841\u2013850, 2010.","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9_CR54","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"T.\u00a0Johnson, N.\u00a0Robertson, P.D. Seymour, and R.\u00a0Thomas. Directed Tree-Width. J. Combin. Theory Ser. B, 82(1):138\u2013154, 2001.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR55","unstructured":"L.\u00a0Kaiser, S.\u00a0Kreutzer, R.\u00a0Rabinovich, and S.\u00a0Siebertz. Directed width measures and monotonicity of directed graph searching. CoRR, arXiv:1408.4745 , 2014."},{"key":"9_CR56","unstructured":"M.M. Kant\u00e9. The rank-width of directed graphs. arXiv:0709.1433 , September 2007."},{"issue":"8","key":"9_CR57","doi-asserted-by":"publisher","first-page":"1820","DOI":"10.1016\/j.ejc.2012.03.034","volume":"33","author":"MM Kant\u00e9","year":"2012","unstructured":"M.M. Kant\u00e9. Well-quasi-ordering of matrices under Schur complement and applications to directed graphs. European J. Combin., 33(8):1820\u20131841, 2012.","journal-title":"European J. Combin."},{"key":"9_CR58","doi-asserted-by":"crossref","unstructured":"M.M. Kant\u00e9 and M.\u00a0Rao. Directed rank-width and displit decomposition. In C.\u00a0Paul and M.\u00a0Habib, editors, WG 2009: Graph-Theoretic Concepts in Computer Science, volume 5911 of Lect. Notes Comput. Sci., pages 214\u2013225. Springer Berlin Heidelberg, 2010.","DOI":"10.1007\/978-3-642-11409-0_19"},{"issue":"4","key":"9_CR59","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/s00224-012-9399-y","volume":"52","author":"MM Kant\u00e9","year":"2013","unstructured":"M.M. Kant\u00e9 and M.\u00a0Rao. The rank-width of edge-coloured graphs. Theory Comput. Syst., 52(4):599\u2013644, 2013.","journal-title":"Theory Comput. Syst."},{"key":"9_CR60","doi-asserted-by":"crossref","unstructured":"K.\u00a0Kawarabayashi, Y.\u00a0Kobayashi, and S.\u00a0Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In STOC 2014: The ACM Symposium on Theory of Computing, pages 70\u201378, New York, NY, USA, 2014. ACM.","DOI":"10.1145\/2591796.2591876"},{"key":"9_CR61","doi-asserted-by":"crossref","unstructured":"K.\u00a0Kawarabayashi and S.\u00a0Kreutzer. The directed grid theorem. In STOC 2015: 47th Annual ACM on Symposium on Theory of Computing, pages 655\u2013664. ACM, 2015.","DOI":"10.1145\/2746539.2746586"},{"key":"9_CR62","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1023\/B:ORDE.0000026489.93166.cb","volume":"20","author":"HA Kierstead","year":"2003","unstructured":"H.A. Kierstead and D.\u00a0Yang. Orderings on graphs and game coloring number. Order, 20:255\u2013264, 2003.","journal-title":"Order"},{"key":"9_CR63","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2016.10.010","volume":"659","author":"S Kintali","year":"2017","unstructured":"S.\u00a0Kintali. Directed width parameters and circumference of digraphs. Theor. Comput. Sci., 659:83\u201387, 2017.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR64","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/j.tcs.2014.10.009","volume":"562","author":"S Kintali","year":"2015","unstructured":"S.\u00a0Kintali, N.\u00a0Kothari, and A.\u00a0Kumar. Approximation algorithms for digraph width parameters. Theor. Comput. Sci., 562:365 \u2013 376, 2015.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR65","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2016.12.008","volume":"662","author":"S Kintali","year":"2017","unstructured":"S.\u00a0Kintali and Q.\u00a0Zhang. Forbidden directed minors and kelly-width. Theor. Comput. Sci., 662:40 \u2013 47, 2017.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR66","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/s00453-015-0015-9","volume":"75","author":"K Kitsunai","year":"2016","unstructured":"K.\u00a0Kitsunai, Y.\u00a0Kobayashi, K.\u00a0Komuro, H.\u00a0Tamaki, and T.\u00a0Tano. Computing directed pathwidth in $$O(1.89^n)$$ time. Algorithmica, 75(1):138\u2013157, 2016.","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"9_CR67","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D Kobler","year":"2003","unstructured":"D.\u00a0Kobler and U.\u00a0Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Appl. Math., 126(2-3):197\u2013221, 2003.","journal-title":"Discrete Appl. Math."},{"key":"9_CR68","doi-asserted-by":"crossref","unstructured":"S.\u00a0Kreutzer. Graph searching games. In K.R. Apt and E.\u00a0Gr\u00e4del, editors, Lectures in Game Theory for Computer Scientists, chapter\u00a07, pages 213\u2013263. Cambridge University Press, 2011.","DOI":"10.1017\/CBO9780511973468.008"},{"issue":"35","key":"9_CR69","doi-asserted-by":"publisher","first-page":"4688","DOI":"10.1016\/j.tcs.2011.05.003","volume":"412","author":"S Kreutzer","year":"2011","unstructured":"S.\u00a0Kreutzer and S.\u00a0Ordyniak. Digraph decompositions and monotonicity in digraph searching. Theor. Comput. Sci., 412(35):4688\u20134703, 2011.","journal-title":"Theor. Comput. Sci."},{"key":"9_CR70","first-page":"181","volume-title":"Discrete Mathematics and Its Applications","author":"Stephan Kreutzer","year":"2014","unstructured":"S.\u00a0Kreutzer and S.\u00a0Ordyniak. Width-measures for directed graphs and algorithmic applications. In Quantitative graph theory, Discrete Math. Appl. (Boca Raton), pages 181\u2013231. CRC Press, Boca Raton, FL, 2015."},{"key":"9_CR71","unstructured":"S.\u00a0Kreutzer, R.\u00a0Rabinovich, S.\u00a0Siebertz, and G.\u00a0Weberst\u00e4dt. Structural properties and constant factor-approximation of strong distance-$$r$$ dominating sets in sparse directed graphs. In STACS 2017: 34th International Symposium on Theoretical Aspects of Computer Science, 2017."},{"key":"9_CR72","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/1.9781611973099.123","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Stephan Kreutzer","year":"2012","unstructured":"S.\u00a0Kreutzer and S.\u00a0Tazari. Directed nowhere dense classes of graphs. In SODA 2012: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1552\u20131562, 2012."},{"issue":"7","key":"9_CR73","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1016\/j.dam.2009.09.018","volume":"158","author":"D Meister","year":"2010","unstructured":"D.\u00a0Meister, J.A. Telle, and M.\u00a0Vatshelle. Recognizing digraphs of Kelly-width 2. Discrete Appl. Math., 158(7):741\u2013746, 2010.","journal-title":"Discrete Appl. Math."},{"key":"9_CR74","doi-asserted-by":"crossref","unstructured":"J.\u00a0Ne\u0161et\u0159il and P.O. de\u00a0Mendez. Grad and classes with bounded expansion I\u2013III. European J. Combin., 29, 2008. Series of $$3$$ papers appearing in volumes $$(3)$$ and $$(4)$$.","DOI":"10.1016\/j.ejc.2007.11.019"},{"issue":"4","key":"9_CR75","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"J.\u00a0Ne\u0161et\u0159il and P.O. de\u00a0Mendez. On nowhere dense graphs. European J. Combin., 32(4):600\u2013617, 2011.","journal-title":"European J. Combin."},{"key":"9_CR76","doi-asserted-by":"crossref","unstructured":"J.\u00a0Obdr\u017e\u00e1lek. Clique-width and parity games. In CSL 2007\/EACSL 2007: 21st International Conference, and the 16th Annuall Conference on Computer Science Logic, volume 4646 of Lect. Notes Comput. Sci., pages 54\u201368, Berlin, Heidelberg, 2007. Springer-Verlag.","DOI":"10.1007\/978-3-540-74915-8_8"},{"key":"9_CR77","unstructured":"J.\u00a0Obdr\u017e\u00e1lek. DAG-width: connectivity measure for directed graphs. In SODA 2006: Symp. on Discrete Algorithms, pages 814\u2013821, 2006."},{"issue":"1","key":"9_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1435375.1435385","volume":"5","author":"Sang-Il Oum","year":"2008","unstructured":"S.\u00a0Oum. Approximating rank-width and clique-width quickly. ACM Trans. Algorithms, 5(1):Art. 10, 20, 2009.","journal-title":"ACM Transactions on Algorithms"},{"key":"9_CR79","doi-asserted-by":"crossref","unstructured":"S.\u00a0Oum. Rank-width: Algorithmic and structural results. Discrete Appl. Math., 2016.","DOI":"10.1016\/j.dam.2016.08.006"},{"issue":"1","key":"9_CR80","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"S.\u00a0Oum. Rank-width and vertex-minors. J. Combin. Theory Ser. B, 95(1):79\u2013100, 2005.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"9_CR81","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1137\/050629616","volume":"22","author":"S Oum","year":"2008","unstructured":"S.\u00a0Oum. Rank-width and well-quasi-ordering. SIAM J. Discrete Math., 22(2):666\u2013682, 2008.","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"9_CR82","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"S.\u00a0Oum and P.D. Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514\u2013528, 2006.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR83","unstructured":"R.\u00a0Rabinovich. Graph Complexity Measures and Monotonicity. PhD thesis, RWTH Aachen University, 2013."},{"key":"9_CR84","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S1571-0653(05)80061-7","volume":"3","author":"B Reed","year":"1999","unstructured":"B.\u00a0Reed. Introducing directed tree-width. Elec. Notes Discrete Math., 3:222 \u2013 229, 1999.","journal-title":"Elec. Notes Discrete Math."},{"key":"9_CR85","doi-asserted-by":"crossref","unstructured":"B.\u00a0Reed. Tree width and tangles: A new connectivity measure and some applications. In R.A. Bailey, editor, Surveys in Combinatorics, volume 241, pages 87\u2013162. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511662119.006"},{"issue":"4","key":"9_CR86","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"B Reed","year":"1996","unstructured":"B.\u00a0Reed, N.\u00a0Robertson, P.D. Seymour, and R.\u00a0Thomas. Packing directed circuits. Combinatorica, 16(4):535\u2013554, 1996.","journal-title":"Combinatorica"},{"key":"9_CR87","unstructured":"F.\u00a0Reidl, F.S. Villaamil, and K.\u00a0Stavropoulos. Characterising bounded expansion by neighbourhood complexity. arXiv:1603.09532 , 2016."},{"issue":"2","key":"9_CR88","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"N.\u00a0Robertson and P.D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B, 52(2):153\u2013190, 1991.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"9_CR89","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"N.\u00a0Robertson and P.D. Seymour. Graph minors V. Excluding a planar graph. J. Combin. Theory Ser. B, 41(1):92\u2013114, 1986.","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR90","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/11549345_64","volume-title":"Mathematical Foundations of Computer Science 2005","author":"Mohammad Ali Safari","year":"2005","unstructured":"M.A. Safari. D-width: A more natural measure for directed tree width. In MFCS 2005: Mathematical Foundations of Computer Science, number 3618 in Lect. Notes Comput. Sci., pages 745 \u2013 756, 2005."},{"issue":"1","key":"9_CR91","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"N.\u00a0Sauer. On the density of families of sets. J. Combin. Theory Ser. A, 13(1):145\u2013147, 1972.","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1","key":"9_CR92","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"PD Seymour","year":"1993","unstructured":"P.D. Seymour and R.\u00a0Thomas. Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B, 58(1):22\u201333, 1993.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"9_CR93","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"S.\u00a0Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41(1):247\u2013261, 1972.","journal-title":"Pacific J. Math."},{"key":"9_CR94","unstructured":"B.\u00a0Sheppard. DNA sequencing by hybridization. Master\u2019s thesis, Memorial University of Newfoundland, 2014."},{"issue":"1","key":"9_CR95","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/070697781","volume":"24","author":"A Slivkins","year":"2010","unstructured":"A.\u00a0Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math., 24(1):146\u2013157, 2010.","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR96","doi-asserted-by":"crossref","unstructured":"H.\u00a0Tamaki. A directed path-decomposition approach to exactly identifying attractors of boolean networks. In ISCIT 2010: International Symposium on Communications and Information Technologies, pages 844\u2013849, Oct 2010.","DOI":"10.1109\/ISCIT.2010.5665106"},{"key":"9_CR97","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-25870-1_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Hisao Tamaki","year":"2011","unstructured":"H.\u00a0Tamaki. A polynomial time algorithm for bounded directed pathwidth. In Graph-Theoretic Concepts in Computer Science, volume 6986 of Lecture Notes in Computer Science, pages 331\u2013342. Springer Berlin Heidelberg, 2011."},{"key":"9_CR98","volume-title":"Matroid decomposition","author":"K Truemper","year":"1992","unstructured":"K.\u00a0Truemper. Matroid decomposition. Academic Press, Inc., Boston, MA, 1992."},{"key":"9_CR99","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-319-21852-6_3","volume-title":"Measures of Complexity","author":"V. N. Vapnik","year":"2015","unstructured":"V.N. Vapnik and A.Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In V.\u00a0Vovk, H.\u00a0Papadopoulos, and A.\u00a0Gammerman, editors, Measures of Complexity, pages 11\u201330. Springer, 2015."},{"issue":"2","key":"9_CR100","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E Wanke","year":"1994","unstructured":"E.\u00a0Wanke. $$k$$-NLC graphs and polynomial algorithms. Discrete Appl. Math., 54(2):251 \u2013 266, 1994.","journal-title":"Discrete Appl. Math."},{"key":"9_CR101","unstructured":"D.H. Younger. Graphs with interlinked directed circuits,. In Midwest symposium on circuit theory 2, pages XVI 2.1\u2013XVI 2.7, 1973."},{"issue":"18","key":"9_CR102","doi-asserted-by":"publisher","first-page":"5562","DOI":"10.1016\/j.disc.2008.03.024","volume":"309","author":"X Zhu","year":"2009","unstructured":"X.\u00a0Zhu. Colouring graphs with bounded generalized colouring number. Discrete Math., 309(18):5562\u20135568, 2009.","journal-title":"Discrete Math."}],"container-title":["Springer Monographs in Mathematics","Classes of Directed Graphs"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71840-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T22:32:54Z","timestamp":1661466774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-71840-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319718392","9783319718408"],"references-count":102,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71840-8_9","relation":{},"ISSN":["1439-7382","2196-9922"],"issn-type":[{"type":"print","value":"1439-7382"},{"type":"electronic","value":"2196-9922"}],"subject":[],"published":{"date-parts":[[2018]]}}}