{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:49Z","timestamp":1740109309049,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00806-x","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T10:33:04Z","timestamp":1612866784000},"page":"1861-1884","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs"],"prefix":"10.1007","volume":"83","author":[{"given":"Jayakrishnan","family":"Madathil","sequence":"first","affiliation":[]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,8]]},"reference":[{"key":"806_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5\u201312, 2009, Proceedings, Part I, pp. 49\u201358 (2009)","DOI":"10.1007\/978-3-642-02927-1_6"},{"issue":"4","key":"806_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"806_CR3","volume-title":"Digraphs\u2014Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2002","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs\u2014Theory, Algorithms and Applications. Springer, Berlin (2002)"},{"issue":"3","key":"806_CR4","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/3196276","volume":"14","author":"F Barbero","year":"2018","unstructured":"Barbero, F., Paul, C., Pilipczuk, M.: Exploring the complexity of layout parameters in tournaments and semicomplete digraphs. ACM Trans. Algorithms 14(3), 38:1\u201338:31 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"806_CR5","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1002\/jgt.22408","volume":"90","author":"F Barbero","year":"2019","unstructured":"Barbero, F., Paul, C., Pilipczuk, M.: Strong immersion is a well-quasi-ordering for semicomplete digraphs. J. Graph Theory 90(4), 484\u2013496 (2019)","journal-title":"J. Graph Theory"},{"issue":"6","key":"806_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, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6), 1071\u20131078 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"806_CR7","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0221016","volume":"21","author":"TN Bui","year":"1992","unstructured":"Bui, T.N., Peck, A.: Partitioning planar graphs. SIAM J. Comput. 21(2), 203\u2013215 (1992)","journal-title":"SIAM J. Comput."},{"issue":"21","key":"806_CR8","first-page":"2151","volume":"249","author":"P Camion","year":"1959","unstructured":"Camion, P.: Chemins et circuits hamiltoniens des graphes complets. Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie des Sciences 249(21), 2151\u20132152 (1959)","journal-title":"Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie des Sciences"},{"issue":"1","key":"806_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2010.10.003","volume":"101","author":"M Chudnovsky","year":"2011","unstructured":"Chudnovsky, M., Seymour, P.D.: A well-quasi-order for tournaments. J. Comb. Theory Ser. B 101(1), 47\u201353 (2011)","journal-title":"J. Comb. Theory Ser. B"},{"key":"806_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"2","key":"806_CR11","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1137\/140988553","volume":"48","author":"M Cygan","year":"2019","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed-parameter tractable. SIAM J. Comput. 48(2), 417\u2013450 (2019)","journal-title":"SIAM J. Comput."},{"key":"806_CR12","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Mertzios, G.B.: Minimum bisection is NP-hard on unit disk graphs. In: Mathematical Foundations of Computer Science 2014\u201439th International Symposium, MFCS 2014, Budapest, Hungary, August 25\u201329, 2014. Proceedings, Part II, pp. 251\u2013262 (2014)","DOI":"10.1007\/978-3-662-44465-8_22"},{"key":"806_CR13","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn, volume 173 of Graduate texts in mathematics. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"issue":"1","key":"806_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.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8(1), 76\u201386 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"806_CR15","unstructured":"Feige, U.: Faster fast (feedback arc set in tournaments). CoRR arXiv:abs\/0911.5094 (2009)"},{"issue":"1","key":"806_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(03)00251-5","volume":"87","author":"U Feige","year":"2003","unstructured":"Feige, U., Yahalom, O.: On the complexity of finding balanced oneway cuts. Inf. Process. Lett. 87(1), 1\u20135 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"806_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-014-9928-y","volume":"71","author":"AE Feldmann","year":"2015","unstructured":"Feldmann, A.E., Widmayer, P.: An o(n$${}^{\\text{4 }}$$) time algorithm to compute the bisection width of solid grid graphs. Algorithmica 71(1), 181\u2013200 (2015)","journal-title":"Algorithmica"},{"key":"806_CR18","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.jctb.2019.01.006","volume":"138","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Pilipczuk, M.: On width measures and topological problems on semi-complete digraphs. J. Comb. Theory Ser. B 138, 78\u2013165 (2019)","journal-title":"J. Comb. Theory Ser. B"},{"key":"806_CR19","unstructured":"Fradkin, A.: Forbidden structures and algorithms in graphs and digraphs. PhD thesis, Princeton University (2011)"},{"issue":"3","key":"806_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"806_CR21","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/S009753970139567X","volume":"35","author":"K Jansen","year":"2005","unstructured":"Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. SIAM J. Comput. 35(1), 110\u2013119 (2005)","journal-title":"SIAM J. Comput."},{"key":"806_CR22","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. In: Algorithms and Computation\u201421st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15\u201317, 2010, Proceedings, Part I, pp. 3\u201314 (2010)","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"806_CR23","unstructured":"Kim, I.: On containment relations in directed graphs. PhD thesis, Princeton University (2013)"},{"key":"806_CR24","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.jctb.2014.12.005","volume":"112","author":"I Kim","year":"2015","unstructured":"Kim, I., Seymour, P.D.: Tournament minors. J. Comb. Theory Ser. B 112, 138\u2013153 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"806_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.disopt.2010.03.010","volume":"8","author":"M Lampis","year":"2011","unstructured":"Lampis, M., Kaouri, G., Mitsou, V.: On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optim. 8(1), 129\u2013138 (2011)","journal-title":"Discrete Optim."},{"key":"806_CR26","unstructured":"Macgregor, R.M.: On partitioning a graph: a theoretical and empirical study. PhD thesis, University of California, Berkeley (1979)"},{"key":"806_CR27","unstructured":"Madathil, J., Sharma, R., Zehavi, M.: A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. In: Rossmanith, P., Heggernes, P., Katoen, J.-P. (es) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26\u201330, 2019, Aachen, Germany, volume 138 of LIPIcs, pp. 28:1\u201328:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"3","key":"806_CR28","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"806_CR29","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 182\u2013191 (1995)"},{"key":"806_CR30","doi-asserted-by":"crossref","unstructured":"Panolan, F., Saurabh, S., Zehavi, M.: Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 1035\u20131054 (2019)","DOI":"10.1137\/1.9781611975482.64"},{"issue":"2","key":"806_CR31","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01305310","volume":"29","author":"CH Papadimitriou","year":"1996","unstructured":"Papadimitriou, C.H., Sideri, M.: The bisection width of grid graphs. Math. Syst. Theory 29(2), 97\u2013110 (1996)","journal-title":"Math. Syst. Theory"},{"key":"806_CR32","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17\u201320, 2008, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"806_CR33","first-page":"39","volume":"7","author":"L R\u00e9dei","year":"1934","unstructured":"R\u00e9dei, L.: Ein kombinatorischer satz. Satz. Acta Litt. Szeged 7, 39\u201343 (1934)","journal-title":"Satz. Acta Litt. Szeged"},{"key":"806_CR34","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Feldmann, A.E., Sorge, M., Such\u00fd, O.: On the parameterized complexity of computing graph bisections. In Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science\u201439th International Workshop, WG 2013, L\u00fcbeck, Germany, June 19\u201321, 2013, Revised Papers, volume 8165 of Lecture Notes in Computer Science, pp. 76\u201387. Springer (2013)","DOI":"10.1007\/978-3-642-45043-3_8"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00806-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00806-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00806-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T23:56:06Z","timestamp":1671148566000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00806-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,8]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["806"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00806-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,2,8]]},"assertion":[{"value":"22 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not Applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code Availability"}}]}}