{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:46:44Z","timestamp":1773272804165,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:00:00Z","timestamp":1573084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:00:00Z","timestamp":1573084800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["NI 369\/16"],"award-info":[{"award-number":["NI 369\/16"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["NI 369\/17"],"award-info":[{"award-number":["NI 369\/17"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100011264","name":"FP7 People: Marie-Curie Actions","doi-asserted-by":"crossref","award":["631163.11"],"award-info":[{"award-number":["631163.11"]}],"id":[{"id":"10.13039\/100011264","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["551145\/14"],"award-info":[{"award-number":["551145\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s10878-019-00464-4","type":"journal-article","created":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T18:02:59Z","timestamp":1573149779000},"page":"216-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient algorithms for measuring the funnel-likeness of DAGs"],"prefix":"10.1007","volume":"39","author":[{"given":"Marcelo","family":"Garlet\u00a0Millani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,7]]},"reference":[{"key":"464_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jcss.2017.07.008","volume":"92","author":"A Agrawal","year":"2018","unstructured":"Agrawal A, Saurabh S, Sharma R, Zehavi M (2018) Kernels for deletion to classes of acyclic digraphs. J Comput Syst Sci 92:9\u201321","journal-title":"J Comput Syst Sci"},{"issue":"8","key":"464_CR2","doi-asserted-by":"publisher","first-page":"1880","DOI":"10.1007\/s00224-018-9852-7","volume":"62","author":"A Agrawal","year":"2018","unstructured":"Agrawal A, Saurabh S, Sharma R, Zehavi M (2018) Parameterised algorithms for deletion to classes of DAGs. Theory Comput Syst 62(8):1880\u20131909","journal-title":"Theory Comput Syst"},{"issue":"8","key":"464_CR3","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1016\/j.ic.2007.02.006","volume":"205","author":"N Ailon","year":"2007","unstructured":"Ailon N, Alon N (2007) Hardness of fully dense problems. Inf Comput 205(8):1117\u20131129","journal-title":"Inf Comput"},{"key":"464_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71840-8","volume-title":"Classes of directed graphs. Springer Monographs in Mathematics Springer","author":"J Bang-Jensen","year":"2018","unstructured":"Bang-Jensen J, Gutin G (2018) Classes of directed graphs. Springer Monographs in Mathematics Springer. Springer, Berlin"},{"key":"464_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs: theory, algorithms and applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen J, Gutin GZ (2009) Digraphs: theory, algorithms and applications. Springer, Berlin"},{"issue":"6","key":"464_CR6","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1016\/j.jcss.2010.10.001","volume":"77","author":"S Bessy","year":"2011","unstructured":"Bessy S, Fomin FV, Gaspers S, Paul C, Perez A, Saurabh S, Thomass\u00e9 S (2011) Kernels for feedback arc set in tournaments. J Comput Syst Sci 77(6):1071\u20131078","journal-title":"J Comput Syst Sci"},{"key":"464_CR7","first-page":"122","volume-title":"Lecture Notes in Computer Science","author":"Paul Bonsma","year":"2011","unstructured":"Bonsma P, Lokshtanov D (2011) Feedback vertex set in mixed graphs. In: Proceedings of the 12th international symposium on algorithms and data structures (WADS \u201911), LNCS, vol 6844, pp 122\u2013133. Springer, Berlin"},{"issue":"3","key":"464_CR8","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai L (2003) Parameterized complexity of vertex colouring. Discrete Appl Math 127(3):415\u2013429","journal-title":"Discrete Appl Math"},{"issue":"1","key":"464_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548306007887","volume":"16","author":"P Charbit","year":"2007","unstructured":"Charbit P, Thomass\u00e9 S, Yeo A (2007) The minimum feedback arc set problem is NP-hard for tournaments. Combin Probab Comput 16(1):1\u20134","journal-title":"Combin Probab Comput"},{"issue":"5","key":"464_CR10","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 (2008) A fixed-parameter algorithm for the directed feedback vertex set problem. J ACM 55(5):21","journal-title":"J ACM"},{"issue":"4","key":"464_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2700209","volume":"11","author":"R Chitnis","year":"2015","unstructured":"Chitnis R, Cygan M, Hajiaghayi M, Marx D (2015) Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans Algorithms 11(4):28","journal-title":"ACM Trans Algorithms"},{"key":"464_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parametr Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, \u0141ukasz K, Marx DLD, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parametr Algorithms. Springer International Publishing, Berlin"},{"key":"464_CR13","volume-title":"Graph theory. Graduate texts in mathematics","author":"R Diestel","year":"2016","unstructured":"Diestel R (2016) Graph theory. Graduate texts in mathematics, vol 173, 5th edn. Springer, Belrin","edition":"5"},{"issue":"1","key":"464_CR14","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","volume":"8","author":"M Dom","year":"2010","unstructured":"Dom M, Guo J, H\u00fcffner F, Niedermeier R, Tru\u00df A (2010) Fixed-parameter tractability results for feedback set problems in tournaments. J Discrete Algorithms 8(1):76\u201386","journal-title":"J Discrete Algorithms"},{"key":"464_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in computer science","author":"RG Downey","year":"2013","unstructured":"Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer, Berlin"},{"issue":"4","key":"464_CR16","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of $$\\ln n$$ for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"issue":"2","key":"464_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 (1980) The directed subgraph homeomorphism problem. Theor Comput Sci 10(2):111\u2013121","journal-title":"Theor Comput Sci"},{"key":"464_CR18","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, Hlinen\u00fd P, Kneis J, Langer A, Obdrz\u00e1lek J, Rossmanith P (2014) Digraph width measures in parameterized algorithmics. Discrete Appl Math 168:88\u2013107","journal-title":"Discrete Appl Math"},{"key":"464_CR19","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, Hlinen\u00fd P, Kneis J, Meister D, Obdrz\u00e1lek J, Rossmanith P, Sikdar S (2016) Are there any good digraph width measures? J Combin Theory Ser B 116:250\u2013286","journal-title":"J Combin Theory Ser B"},{"key":"464_CR20","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"Jiong Guo","year":"2004","unstructured":"Guo J, H\u00fcffner F, Niedermeier R (2004) A structural view on parameterizing problems: distance from triviality. In: Proceedings of the 1st international workshop on parameterized and exact computation (IWPEC \u201904), pp 162\u2013173. Springer, Berlin"},{"issue":"2","key":"464_CR21","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of $$k$$-SAT. J Comput Syst Sci 62(2):367\u2013375","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"464_CR22","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"464_CR23","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 PD, Thomas R (2001) Directed tree-width. J Combin Theory Ser B 82(1):138\u2013154","journal-title":"J Combin Theory Ser B"},{"key":"464_CR24","doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu C, Schudy W (2007) How to rank with few errors. In: Proceedings of the 39th ACM symposium on theory of computing (STOC \u201907), pp 95\u2013103. ACM","DOI":"10.1145\/1250790.1250806"},{"key":"464_CR25","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) KONECT\u2014The Koblenz network collection. In: Proceedings of the 22nd international world wide web conference (WWW \u201913), pp 1343\u20131350. ACM","DOI":"10.1145\/2487788.2488173"},{"key":"464_CR26","unstructured":"Lehmann J (2017) The computational complexity of worst case flows in unreliable flow networks. Bachelor thesis, Institut f\u00fcr Theoretische Informatik, Universit\u00e4t zu L\u00fcbeck"},{"key":"464_CR27","doi-asserted-by":"crossref","unstructured":"Leskovec J, Backstrom L, Kleinberg J (2009) Meme-tracking and the dynamics of the news cycle. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD \u201909), pp 497\u2013506. ACM","DOI":"10.1145\/1557019.1557077"},{"key":"464_CR28","doi-asserted-by":"crossref","unstructured":"Lund C, Yannakakis M (1993) The approximation of maximum subgraph problems. In: Proceedings of the 20th international colloquium on automata, languages, and programming (ICALP \u201993), LNCS, vol 700, pp 40\u201351. Springer","DOI":"10.1007\/3-540-56939-1_60"},{"key":"464_CR29","unstructured":"Millani MG (2017) Funnels\u2014algorithmic complexity of problems on special directed acyclic graphs. Master thesis, Algorithmics and computational complexity (AKT), TU\u00a0Berlin. \nhttp:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/MA-marcelo-millani.pdf"},{"key":"464_CR30","unstructured":"Millani MG (2017) Parfunn\u2014parameters for funnels. \nhttps:\/\/gitlab.tubit.tu-berlin.de\/mgmillani1\/parfunn"},{"key":"464_CR31","doi-asserted-by":"crossref","unstructured":"Millani MG, Molter H, Niedermeier R, Sorge M (2018) Efficient algorithms for measuring the funnel-likeness of DAGs. In: Proceedings of the 5th international symposium on combinatorial optimization (ISCO \u201918), LNCS, vol 10856, pp 183\u2013195. Springer","DOI":"10.1007\/978-3-319-96151-4_16"},{"key":"464_CR32","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","volume":"25","author":"M Mnich","year":"2017","unstructured":"Mnich M, van Leeuwen EJ (2017) Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim 25:48\u201376","journal-title":"Discrete Optim"},{"key":"464_CR33","unstructured":"Niedermeier R (2010) Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS \u201910), pp 17\u201332. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"key":"464_CR34","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.dam.2016.12.002","volume":"220","author":"R van Bevern","year":"2017","unstructured":"van Bevern R, Bredereck R, Chopin M, Hartung S, H\u00fcffner F, Nichterlein A, Such\u00fd O (2017) Fixed-parameter algorithms for DAG partitioning. Discrete Appl Math 220:134\u2013160","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00464-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00464-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00464-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,6]],"date-time":"2020-11-06T00:48:11Z","timestamp":1604623691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00464-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,7]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["464"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00464-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,7]]},"assertion":[{"value":"7 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}