k-distinct in- and out-branchings in digraphs

Journal of Computer and System Sciences - Tập 95 - Trang 86-97 - 2018
Gregory Gutin1, Felix Reidl2, Magnus Wahlström1
1Royal Holloway, University of London, UK
2North Carolina State University, USA

Tài liệu tham khảo

Alon, 2009, Spanning directed trees with many leaves, SIAM J. Discrete Math., 23, 466, 10.1137/070710494 Bang-Jensen, 1991, Edge-disjoint in- and out-branchings in tournaments and related path problems, J. Comb. Theory, Ser. B, 51, 1, 10.1016/0095-8956(91)90002-2 Bang-Jensen, 2002 Bang-Jensen, 1995, Quasi-transitive digraphs, J. Graph Theory, 20, 141, 10.1002/jgt.3190200205 Bang-Jensen, 2014, Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs, J. Graph Theory, 77, 278, 10.1002/jgt.21786 Bang-Jensen, 2016, Parameterized algorithms for non-separating trees and branchings in digraphs, Algorithmica, 76, 279, 10.1007/s00453-015-0037-3 Bang-Jensen, 2013, Arc-disjoint paths and trees in 2-regular digraphs, Discrete Appl. Math., 161, 2724, 10.1016/j.dam.2013.04.018 Bang-Jensen, 2003, Small degree out-branchings, J. Graph Theory, 42, 297, 10.1002/jgt.10092 Bang-Jensen, 2008, The minimum spanning strong subdigraph problem is fixed parameter tractable, Discrete Appl. Math., 156, 2924, 10.1016/j.dam.2007.12.003 Bérczi, 2009, A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph, Inf. Process. Lett., 109, 1227, 10.1016/j.ipl.2009.09.004 Cygan, 2015 Daligault, 2010, FPT algorithms and kernels for the directed k-leaf problem, J. Comput. Syst. Sci., 76, 144, 10.1016/j.jcss.2009.06.005 Downey, 2013 Edmonds, 1967, Optimum branchings, J. Res. Natl. Bur. Stand. B, 71B, 233, 10.6028/jres.071B.032 Edmonds, 1973, Edge-disjoint branchings, 91 Fradkin, 2013, Tournament pathwidth and topological containment, J. Comb. Theory, Ser. B, 103, 374, 10.1016/j.jctb.2013.03.001 Kawarabayashi, 2015, The directed grid theorem, 655 Kim, 2015, Tournament minors, J. Comb. Theory, Ser. B, 112, 138, 10.1016/j.jctb.2014.12.005 Kneis, 2011, A new algorithm for finding trees with many leaves, Algorithmica, 61, 882, 10.1007/s00453-010-9454-5