{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:54Z","timestamp":1759638774901,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_15","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"185-197","source":"Crossref","is-referenced-by-count":16,"title":["On Digraph Width Measures in Parameterized Algorithmics"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Kneis","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Langer","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Obdr\u017e\u00e1lek","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J. Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics\u00a022(2), 161\u2013172 (2006)","journal-title":"Graphs and Combinatorics"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"15_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Berwanger","year":"2005","unstructured":"Berwanger, D., Gr\u00e4del, E.: Entanglement \u2013 a measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 209\u2013223. Springer, Heidelberg (2005)"},{"key":"15_CR4","unstructured":"Bang-Jensen, J., Kriesell, M.: Disjoint directed and undirected paths and cycles in digraphs. Technical Report PP-2009-03, University of South Denmark (2009)"},{"key":"15_CR5","volume-title":"Principles of Model Checking","author":"C. Baier","year":"2008","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. The MIT Press, Cambridge (2008)"},{"key":"15_CR6","unstructured":"Bui-Xuan, B.-M., Telle, J., Vatshelle, M.: H-join and algorithms on graphs of bounded rank-width (submitted) (November 2008)"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11611257_20","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"J.-F. Culus","year":"2006","unstructured":"Culus, J.-F., Demange, M.: Oriented coloring: Complexity and approximation. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol.\u00a03831, pp. 226\u2013236. Springer, Heidelberg (2006)"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-74839-7_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"2007","unstructured":"Courcelle, B., Kant\u00e9, M.: Graph operations characterizing rank-width and balanced graph expressions. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 66\u201375. Springer, Heidelberg (2007)"},{"issue":"6","key":"15_CR9","doi-asserted-by":"crossref","first-page":"2526","DOI":"10.1137\/080716475","volume":"38","author":"J. Chen","year":"2009","unstructured":"Chen, J., Kneis, J., Lu, S., M\u00f6lle, D., Richter, S., Rossmanith, P., Sze, S., Zhang, F.: Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM Journal on Computing\u00a038(6), 2526\u20132547 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"15_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"15_CR11","unstructured":"Dankelmann, P., Gutin, G., Kim, E.: On complexity of minimun leaf out-branching. arXiv:0808.0980v1 (August 2008)"},{"issue":"4","key":"15_CR12","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L. Eggan","year":"1963","unstructured":"Eggan, L.: Transition graphs and the star-height of regular events. Michigan Mathematical Journal\u00a010(4), 385\u2013397 (1963)","journal-title":"Michigan Mathematical Journal"},{"key":"15_CR13","first-page":"825","volume-title":"SODA 2009","author":"F. Fomin","year":"2009","unstructured":"Fomin, F., Golovach, P., Lokshtanov, D., Saurab, S.: Clique-width: On the price of generality. In: SODA 2009, pp. 825\u2013834. SIAM, Philadelphia (2009)"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR15","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: Automata approach to graphs of bounded rank-width. In: IWOCA 2008, pp. 4\u201315 (2008)"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-642-10217-2_27","volume-title":"IWOCA 2009","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: Better polynomial algorithms on graphs of bounded rank-width. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol.\u00a05874, pp. 266\u2013277. Springer, Heidelberg (2009)"},{"key":"15_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1979)"},{"key":"15_CR18","unstructured":"Gruber, H.: Digraph complexity measures and applications in formal language theory. In: MEMICS 2008, pp. 60\u201367 (2008)"},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol.\u00a02500. Springer, Heidelberg (2002)"},{"issue":"1-3","key":"15_CR20","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.tcs.2006.02.026","volume":"359","author":"F. Gurski","year":"2006","unstructured":"Gurski, F., Wanke, E.: Vertex disjoint paths on clique-width bounded graphs. Theor. Comput. Sci.\u00a0359(1-3), 188\u2013199 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P. Hunter","year":"2008","unstructured":"Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci.\u00a0399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR22","unstructured":"Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J.: Escape-width: Measuring \u201dwidth\u201d of digraphs. Presented at Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (2006)"},{"key":"15_CR23","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decomposition and rank-decomposition. SIAM J. Comput.\u00a038, 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"key":"15_CR24","series-title":"Annals of Discrete Mathematics","volume-title":"The Steiner Tree Problem","author":"F. Hwang","year":"1992","unstructured":"Hwang, F., Richards, D., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics. North-Holland, Amsterdam (1992)"},{"issue":"1","key":"15_CR25","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. Journal of Combinatorial Theory, Series B\u00a082(1), 138\u2013154 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"15_CR26","unstructured":"Kant\u00e9, M.: The rank-width of directed graphs. arXiv:0709.1433v3 (March 2008)"},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0012-365X(03)00086-4","volume":"274","author":"W. Klostermeyer","year":"2004","unstructured":"Klostermeyer, W., MacGillivray, G.: Homomorphisms and oriented colorings of equivalence classes of oriented graphs. Discrete Mathematics\u00a0274, 161\u2013172 (2004)","journal-title":"Discrete Mathematics"},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-540-92248-3_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Kreutzer","year":"2008","unstructured":"Kreutzer, S., Ordyniak, S.: Digraph decompositions and monotonicity in digraph searching. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 336\u2013347. Springer, Heidelberg (2008)"},{"key":"15_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-540-92182-0_22","volume-title":"Algorithms and Computation","author":"M. Lampis","year":"2008","unstructured":"Lampis, M., Kaouri, G., Mitsou, V.: On the algorithmic effectiveness of digraph decompositions and complexity measures. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 220\u2013231. Springer, Heidelberg (2008)"},{"issue":"6","key":"15_CR30","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin.\u00a027(6), 1024\u20131041 (2006)","journal-title":"European J. Combin."},{"key":"15_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Computer Aided Verification","author":"J. Obdr\u017e\u00e1lek","year":"2003","unstructured":"Obdr\u017e\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol.\u00a02725, pp. 80\u201392. Springer, Heidelberg (2003)"},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1145\/1109557.1109647","volume-title":"SODA 2006","author":"J. Obdr\u017e\u00e1lek","year":"2006","unstructured":"Obdr\u017e\u00e1lek, J.: DAG-width \u2013 connectivity measure for directed graphs. In: SODA 2006, pp. 814\u2013821. ACM-SIAM, New York (2006)"},{"key":"15_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-74915-8_8","volume-title":"Computer Science Logic","author":"J. Obdr\u017e\u00e1lek","year":"2007","unstructured":"Obdr\u017e\u00e1lek, J.: Clique-width and parity games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"issue":"3","key":"15_CR34","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"15_CR35","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory B"},{"key":"15_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/11549345_64","volume-title":"Mathematical Foundations of Computer Science 2005","author":"M. Safari","year":"2005","unstructured":"Safari, M.: D-width: A more natural measure for directed tree-width. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 745\u2013756. Springer, Heidelberg (2005)"},{"key":"15_CR37","unstructured":"van Leeuwen, J.: Having a Grundy-numbering is NP-complete. Technical Report 207, The Pennsylvania State University (September 1976)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T22:11:34Z","timestamp":1675894294000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}