Packing arc-disjoint cycles in oriented graphs
References
[1]
Faisal N. Abu-Khzam, An improved kernelization algorithm for r-set packing, Inf. Process. Lett. 110 (16) (2010) 621–624,.
[2]
Noga Alon, Raphael Yuster, Uri Zwick, Color-coding, J. ACM 42 (4) (1995) 844–856,.
[3]
Jørgen Bang-Jensen, Gregory Z. Gutin, Digraphs – Theory, Algorithms and Applications, Springer Monographs in Mathematics, second edition, Springer, 2009.
[4]
Claude Berge, Graphs and Hypergraphs, North-Holland Pub. Co., 1973.
[5]
Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, Meirav Zehavi, Packing arc-disjoint cycles in tournaments, Algorithmica 83 (5) (2021) 1393–1420,.
[6]
Hans L. Bodlaender, On disjoint cycles, Int. J. Found. Comput. Sci. 5 (1) (1994) 59–68,.
[7]
Hans L. Bodlaender, Bart M.P. Jansen, Stefan Kratsch, Kernel bounds for path and cycle problems, Theor. Comput. Sci. 511 (2013) 117–136,.
[8]
Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo, Kernel bounds for disjoint cycles and disjoint paths, Theor. Comput. Sci. 412 (35) (2011) 4570–4578,.
[9]
Richard A. Brualdi, Jian Shen, Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs, J. Comb. Theory, Ser. B 85 (2) (2002) 189–196,.
[10]
Leizhen Cai, Parameterized complexity of vertex colouring, Discrete Appl. Math. 127 (3) (2003) 415–429,.
[11]
Kevin Chen, Sean Karson, Dan Liu, Jian Shen, On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs, Electron. J. Linear Algebra 28 (2015) 117–123.
[12]
Maria Chudnovsky, Paul D. Seymour, Blair D. Sullivan, Cycles in dense digraphs, Combinatorica 28 (1) (2008) 1–18,.
[13]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer, 2015,.
[14]
Reinhard Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg, 2006.
[15]
Dorit Dor, Michael Tarsi, Graph decomposition is NPC - a complete proof of Holyer's conjecture, in: S. Rao Kosaraju, Mike Fellows, Avi Wigderson, John A. Ellis (Eds.), Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, ACM, 1992, pp. 252–263,.
[16]
Rodney G. Downey, Michael R. Fellows, Fundamentals of Parameterized Complexity, Texts in Computer Science, Springer, 2013,.
[17]
Molly Dunkum, Peter Hamburger, Attila Pór, Destroying cycles in digraphs, Combinatorica 31 (1) (2011) 55–66,.
[18]
Paul Erdős, Lajos Pósa, On independent circuits contained in a graph, Can. J. Math. 17 (1965) 347–352,.
[19]
Paul Erdős, Richard Rado, Intersection theorems for systems of sets, J. Lond. Math. Soc. s1–35 (1) (1960) 85–90,.
[20]
Michael R. Fellows, Bart M.P. Jansen, Frances A. Rosamond, Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity, Eur. J. Comb. 34 (3) (2013) 541–566,.
[21]
Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides, Faster fixed-parameter tractable algorithms for matching and packing problems, Algorithmica 52 (2) (2008) 167–176,.
[22]
Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh, The complexity ecology of parameters: an illustration using bounded max leaf number, Theory Comput. Syst. 45 (4) (2009) 822–848,.
[23]
Jörg Flum, Martin Grohe, Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2006,.
[24]
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi, Subquadratic kernels for implicit 3-hitting set and 3-set packing problems, ACM Trans. Algorithms 15 (1) (2019) 13:1–13:44,.
[25]
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, Kernelization: Theory of Parameterized Preprocessing, Cambridge University Press, 2019.
[26]
András Frank, Éva Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica 7 (1) (1987) 49–65,.
[27]
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
[28]
Ajay Saju Jacob, R. Krithika, Packing arc-disjoint cycles in bipartite tournaments, in: M. Sohel Rahman, Kunihiko Sadakane, Wing-Kin Sung (Eds.), WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Singapore, March 31 - April 2, 2020, Proceedings, in: Lecture Notes in Computer Science, vol. 12049, Springer, 2020, pp. 249–260,.
[29]
Bart M.P. Jansen, The Power of Data Reduction: Kernels for Fundamental Graph Problems, PhD thesis Utrecht University, The Netherlands, 2013.
[30]
Hendrik W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (4) (1983) 538–548,.
[31]
Ravi Kannan, Minkowski's convex body theorem and integer programming, Math. Oper. Res. 12 (3) (1987) 415–440,.
[32]
Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithms 3 (4) (2007) 48,.
[33]
Daniel Lokshtanov, Fahad Panolan, M.S. Ramanujan, Saket Saurabh, Lossy kernelization, in: Hamed Hatami, Pierre McKenzie, Valerie King (Eds.), Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2017, Montreal, QC, Canada, June 19–23, 2017, ACM, 2017, pp. 224–237,.
[34]
Jessica McDonald, Gregory J. Puleo, Craig Tennenhouse, Packing and covering directed triangles, Graphs Comb. 36 (4) (2020) 1059–1063,.
[35]
Hannes Moser, Finding optimal solutions for covering and matching problems, PhD thesis Friedrich Schiller University of Jena, 2010, https://d-nb.info/999819399.
[36]
Moni Naor, Leonard J. Schulman, Aravind Srinivasan, Splitters and near-optimal derandomization, in: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, IEEE Computer Society, 1995, pp. 182–191,.
[37]
Bruce A. Reed, Neil Robertson, Paul D. Seymour, Robin Thomas, Packing directed circuits, Combinatorica 16 (4) (1996) 535–554,.
[38]
Aleksandrs Slivkins, Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM J. Discrete Math. 24 (1) (2010) 146–157,.
[39]
Craig A. Tovey, A simplified NP-complete satisfiability problem, Discrete Appl. Math. 8 (1) (1984) 85–89,.
Recommendations
Packing Arc-Disjoint Cycles in Tournaments
AbstractA tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle ...
Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs
Let R=(r1, , rm) and S=(s1, , sn) be nonnegative integral vectors with ri= sj. Let A(R, S) denote the set of all m n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) . The interchange graphG(R, S) of A(R, S) was defined by ...
Arc-Disjoint Cycles and Feedback Arc Sets
Isaak posed the following problem. Suppose T is a tournament having a minimum feedback arc set, which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc-disjoint cycles in T equals the cardinality of minimum ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier Inc.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 09 July 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024