{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T10:30:46Z","timestamp":1774261846588,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T00:00:00Z","timestamp":1495843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft DFG","award":["MI439\/14-1"],"award-info":[{"award-number":["MI439\/14-1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9777-6","type":"journal-article","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T05:58:04Z","timestamp":1495864684000},"page":"1048-1084","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Exact Localisations of Feedback Sets"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9214-8253","authenticated-orcid":false,"given":"Michael","family":"Hecht","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,27]]},"reference":[{"issue":"1","key":"9777_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N Alon","year":"2006","unstructured":"Alon, N.: Ranking tournaments. SIAM J. Discret. Math. 20(1), 137\u2013142 (2006)","journal-title":"SIAM J. Discret. Math."},{"key":"9777_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York (2009)","edition":"1st edn"},{"key":"9777_CR3","doi-asserted-by":"crossref","unstructured":"Korte, B., Lov\u00e1sz, L.: Mathematical structures underlying greedy algorithms. Fundamentals of Computation Theory, Lecture Notes in Comp. Sci. pages 205\u2013209 (1981)","DOI":"10.1007\/3-540-10854-8_22"},{"key":"9777_CR4","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Publishing Company, Incorporated (2008)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"9777_CR5","volume-title":"Hypergraphs, volume 45 of North-Holland Mathematical Library","author":"C Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs, volume 45 of North-Holland Mathematical Library. Combinatorics of Finite Sets, North-Holland (1989)"},{"key":"9777_CR6","volume-title":"The Theory of Graphs","author":"C Berge","year":"2001","unstructured":"Berge, C.: The Theory of Graphs. Dover books on mathematics, Dover (2001)"},{"key":"9777_CR7","unstructured":"Berger, B., Shor, P.W.: Approximation algorithms for the maximum acyclic subgraph problem. In SODA, pp. 236\u2013243. SIAM (1990)"},{"key":"9777_CR8","volume-title":"Algebraic Graph Theory","author":"N Biggs","year":"1993","unstructured":"Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)","edition":"2nd edn"},{"issue":"5","key":"9777_CR9","doi-asserted-by":"publisher","first-page":"21:1","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:1\u201321:19 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"9777_CR10","first-page":"1277","volume":"194","author":"E Dinic","year":"1970","unstructured":"Dinic, E.: Algortithm for solution of a problem of maximum flow in network with power estimates. Dokl. Akad. Nauk SSSR 194(4), 1277\u20131280 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9777_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/11685654_10","volume-title":"Theoretical Computer Science, Essays in Memory of Shimon Even","author":"Y Dinitz","year":"2006","unstructured":"Dinitz, Y.: Dinitz\u2019 algorithm: The original version and even\u2019s version Theoretical Computer Science, Essays in Memory of Shimon Even, pp 218\u2013240 (2006)"},{"key":"9777_CR12","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math., 162 (2005)","DOI":"10.4007\/annals.2005.162.439"},{"issue":"2","key":"9777_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even, G., (Seffi) Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"issue":"2","key":"9777_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., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9777_CR15","first-page":"91","volume-title":"11th Conference on Information Sciences and Systems","author":"F Gavril","year":"1977","unstructured":"Gavril, F.: Some NP-complete problems on graphs 11th Conference on Information Sciences and Systems, pp 91\u201395 (1977)"},{"issue":"1","key":"9777_CR16","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF01582009","volume":"33","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: On the acyclic subgraph polytope. Math. Program. 33(1), 28\u201342 (1985)","journal-title":"Math. Program."},{"issue":"2","key":"9777_CR17","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"9777_CR18","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1017\/S0963548313000394","volume":"22","author":"H Huang","year":"2013","unstructured":"Huang, H., Ma, J., Shapira, A., Sudakov, B., Yuster, R.: Large feedback arc sets, high minimum degree subgraphs, and long cycles in eulerian digraphs. Comb. Probab. Comput. 22, 859\u2013873 (2013)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"9777_CR19","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1186\/1471-2105-9-424","volume":"9","author":"I Ispolatov","year":"2008","unstructured":"Ispolatov, I., Maslov, S.: Detection of the dominant direction of information flow and feedback links in densely interconnected regulatory networks. BMC Bioinforma. 9(1), 424 (2008)","journal-title":"BMC Bioinforma."},{"issue":"1","key":"9777_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77\u201384 (1975)","journal-title":"SIAM J. Comput."},{"key":"9777_CR21","first-page":"377","volume-title":"STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings","author":"V Kann","year":"1992","unstructured":"Kann, V.: On the approximability of the maximum common subgraph problem STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings, pp 377\u2013388 (1992)"},{"key":"9777_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp 85\u2013103 (1972)"},{"key":"9777_CR23","volume-title":"Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament 3\u201314","author":"M Karpinski","year":"2010","unstructured":"Karpinski, M., Schudy, W.: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament 3\u201314. Springer Berlin Heidelberg, Berlin Heidelberg (2010)"},{"issue":"2","key":"9777_CR24","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF00137392","volume":"1","author":"A Kunzmann","year":"1990","unstructured":"Kunzmann, A., Wunderlich, H.-J.: An analytical approach to the partial scan problem. J. Electron. Test. 1(2), 163\u2013174 (1990)","journal-title":"J. Electron. Test."},{"issue":"1-6","key":"9777_CR25","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01759032","volume":"6","author":"CE Leiserson","year":"1991","unstructured":"Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. Algorithmica 6(1-6), 5\u201335 (1991)","journal-title":"Algorithmica"},{"issue":"3","key":"9777_CR26","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"2, 17","author":"C Lucchesi","year":"1978","unstructured":"Lucchesi, C., Younger, D.: A minimax theorem for directed graphs. J. Lond. Math. Soc. 2, 17(3), 369\u2013374 (1978)","journal-title":"J. Lond. Math. Soc."},{"key":"9777_CR27","doi-asserted-by":"crossref","unstructured":"Mart\u00ed, R.: The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Applied Mathematical Sciences. Springer (2011)","DOI":"10.1007\/978-3-642-16729-4_2"},{"issue":"1","key":"9777_CR28","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1137\/0205007","volume":"5","author":"P Mateti","year":"1976","unstructured":"Mateti, P., Deo, N.: On algorithms for enumerating all circuits of a graph. SIAM J. Comput. 5(1), 90\u201399 (1976)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9777_CR29","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0196-6774(88)90022-3","volume":"9","author":"V Ramachandran","year":"1988","unstructured":"Ramachandran, V.: Finding a minimum feedback arc set in reducible flow graphs. J. Algorithm. 9(3), 299\u2013313 (1988)","journal-title":"J. Algorithm."},{"key":"9777_CR30","first-page":"70","volume-title":"Theoretical Computer Science, 10th Italian Conference, ICTCS 2007, Rome, Italy, October 3-5, 2007, Proceedings","author":"I Razgon","year":"2007","unstructured":"Razgon, I.: Computing minimum directed feedback vertex set in o(1.9977 n) Theoretical Computer Science, 10th Italian Conference, ICTCS 2007, Rome, Italy, October 3-5, 2007, Proceedings, pp 70\u201381 (2007)"},{"key":"9777_CR31","doi-asserted-by":"crossref","unstructured":"Roberts, B., Kroese, D.P.: Estimating the number of s-t paths in a graph. J. Graph Algorithm. Appl. (2007)","DOI":"10.7155\/jgaa.00142"},{"issue":"3","key":"9777_CR32","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1011315014322","volume":"7","author":"Y Saab","year":"2001","unstructured":"Saab, Y.: A fast and effective algorithm for the feedback arc set problem. J. Heuristics 7(3), 235\u2013250 (2001)","journal-title":"J. Heuristics"},{"key":"9777_CR33","unstructured":"Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts. 8th edn. Wiley Publishing (2008)"},{"issue":"3","key":"9777_CR34","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0202017","volume":"2","author":"RE Tarjan","year":"1973","unstructured":"Tarjan, R.E.: Enumeration of the elementary circuits of a directed graph. SIAM J. Comput. 2(3), 211\u2013216 (1973)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9777-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9777-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9777-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T22:29:55Z","timestamp":1659047395000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9777-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,27]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9777"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9777-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,27]]},"assertion":[{"value":"27 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}