{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T10:05:26Z","timestamp":1770890726845,"version":"3.50.1"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030392185","type":"print"},{"value":"9783030392192","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","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":[[2020]]},"DOI":"10.1007\/978-3-030-39219-2_33","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T19:09:24Z","timestamp":1579892964000},"page":"415-426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parameterized Algorithms for Directed Modular Width"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0462-7815","authenticated-orcid":false,"given":"Sebastian","family":"Wiederrecht","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,24]]},"reference":[{"key":"33_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71840-8","volume-title":"Classes of Directed Graphs","author":"J Bang-Jensen","year":"2018","unstructured":"Bang-Jensen, J., Gutin, G.: Classes of Directed Graphs. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-71840-8"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.tcs.2012.03.017","volume":"443","author":"J Bang-Jensen","year":"2012","unstructured":"Bang-Jensen, J., Havet, F., Trotignon, N.: Finding an induced subdivision of a digraph. Theor. Comput. Sci. 443, 10\u201324 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR3","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. 3884, pp. 524\u2013536. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11672142_43"},{"key":"33_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"HL Bodlaender","year":"1997","unstructured":"Bodlaender, H.L.: Treewidth: algorithmic techniques and results. In: Pr\u00edvara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19\u201336. Springer, Heidelberg (1997). \nhttps:\/\/doi.org\/10.1007\/BFb0029946"},{"issue":"5","key":"33_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21 (2008)","journal-title":"J. ACM"},{"issue":"1","key":"33_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing By Graph Transformation: Volume 1: Foundations, pp. 313\u2013400. World Scientific (1997)","DOI":"10.1142\/9789812384720_0005"},{"key":"33_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 138. Cambridge University Press, New York (2012)"},{"issue":"2","key":"33_CR9","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"33_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. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 197\u2013206 (2013)","DOI":"10.1109\/FOCS.2013.29"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248\u2013264 (1972)","journal-title":"J. ACM"},{"issue":"4","key":"33_CR13","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"LC Eggan","year":"1963","unstructured":"Eggan, L.C., et al.: Transition graphs and the star-height of regular events. The Mich. Math. J. 10(4), 385\u2013397 (1963)","journal-title":"The Mich. Math. J."},{"key":"33_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117\u2013128. Springer, Heidelberg (2001). \nhttps:\/\/doi.org\/10.1007\/3-540-45477-2_12"},{"key":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294\u2013305. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-92182-0_28"},{"issue":"5","key":"33_CR16","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"key":"33_CR17","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., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR18","unstructured":"Frank, A.: Packing paths, circuits and cuts-a survey. In: Paths, Flows, and VLSI-Layout, pp. 47\u2013100. Springer-Verlag, Berlin (1990)"},{"key":"33_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"key":"33_CR20","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.jctb.2015.09.001","volume":"116","author":"R Ganian","year":"2016","unstructured":"Ganian, R., et al.: Are there any good digraph width measures? J. Comb. Theory Ser. B 116, 250\u2013286 (2016)","journal-title":"J. Comb. Theory Ser. B"},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.dam.2013.10.038","volume":"168","author":"R Ganian","year":"2014","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., Rossmanith, P.: Digraph width measures in parameterized algorithmics. Discrete Appl. Math. 168, 88\u2013107 (2014)","journal-title":"Discrete Appl. Math."},{"key":"33_CR22","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"issue":"15","key":"33_CR23","doi-asserted-by":"publisher","first-page":"2089","DOI":"10.1016\/j.dam.2012.03.015","volume":"160","author":"AC Giannopoulou","year":"2012","unstructured":"Giannopoulou, A.C., Hunter, P., Thilikos, D.M.: Lifo-search: a min-max theorem and a searching game for cycle-rank and tree-depth. Discrete Appl. Math. 160(15), 2089\u20132097 (2012)","journal-title":"Discrete Appl. Math."},{"key":"33_CR24","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K.I., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC 2011, New York, NY, USA, pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"33_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/978-3-030-25027-0_20","volume-title":"Fundamentals of Computation Theory","author":"F Gurski","year":"2019","unstructured":"Gurski, F., Komander, D., Rehs, C.: Computing digraph width measures on directed co-graphs. In: G\u0105sieniec, L.A., Jansson, J., Levcopoulos, C. (eds.) FCT 2019. LNCS, vol. 11651, pp. 292\u2013305. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-25027-0_20"},{"issue":"3","key":"33_CR26","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. 399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"33_CR27","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., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\u20133","key":"33_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"33_CR29","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.dam.2004.02.017","volume":"145","author":"RM McConnella","year":"2005","unstructured":"McConnella, R.M., de Montgolfier, F.: Linear time modular decomposition of directed graphs. Discrete Appl. Math. 145, 198\u2013209 (2005)","journal-title":"Discrete Appl. Math."},{"key":"33_CR30","unstructured":"Millani, M.G., Steiner, R., Wiederrecht, S.: Colouring non-even digraphs. Technical report (2019, submitted). arXiv Preprint, \narXiv:1903.02872"},{"key":"33_CR31","unstructured":"N.\u00a0Robertson, P.D.S.: An outline of a disjoint paths algorithm. In: Paths, Flows, and VLSI-Layout, pp. 267\u2013292. Springer-Verlag, Berlin (1990)"},{"issue":"4","key":"33_CR32","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inform. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"33_CR33","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. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39219-2_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:02:28Z","timestamp":1579910548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39219-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030392185","9783030392192"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39219-2_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"24 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hyderabad","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iith.ac.in\/~caldam2020\/index.php","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}