On the minimum number of inversions to make a digraph k-(arc-)strong
EUROCOMB’23
386–392
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5), 2008.
https://doi.org/10.1145/1411509.1411513
Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20:137-142, 2006.
https://doi.org/10.1137/050623905
Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer. Invertibility of digraphs and tournaments, 2022.
Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud, and Quentin Vermande. Problems, proofs, and disproofs on the inversion number, 2022.
Jœrgen Bang-Jensen and Anders Yeo. Making a tournament k-arc-strong by reversing or deorienting arcs. Discrete Applied Mathematics, 136(2):161-171, 2004. The 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
https://doi.org/10.1016/S0166-218X(03)00438-4
Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet. On the inversion number of oriented graphs. Discrete Mathematics & Theoretical Computer Science, 23(2):# 8, 2022.
https://doi.org/10.46298/dmtcs.7474
Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs: theory, algorithms and applications. Springer-Verlag, London, 2009.
https://doi.org/10.1007/978-1-84800-998-1
Jørgen Bang-Jensen, Florian Hörsch, and Matthias Kriesell. Complexity of (arc)-connectivity problems involving arc-reversals or deorientations, 2023.
https://doi.org/10.2139/ssrn.4399506
Jørgen Bang-Jensen, Kasper S. Johansen, and Anders Yeo. Making a tournament k-strong. Journal of Graph Theory, 103(1):5-11, 2023.
https://doi.org/10.1002/jgt.22900
Houmem Belkhechine, Moncef Bouaziz, Imed Boudabbous, and Maurice Pouzet. Inversion dans les tournois. Comptes Rendus Mathematique, 348(13-14):703-707, 2010.
https://doi.org/10.1016/j.crma.2010.06.022
Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics, Probability and Computing, 16:1-4, 2007.
https://doi.org/10.1017/S0963548306007887
Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, Second Series, 162(1):439-485, 2005.
https://doi.org/10.4007/annals.2005.162.439
Olivier Durand de Gevigney. On Frank's conjecture on k-connected orientations. Journal of Combinatorial Theory, Series B, 141:105-114, 2020.
https://doi.org/10.1016/j.jctb.2019.07.001
Julien Duron, Frédéric Havet, Florian Hörsch, and Clément Rambaud. On the minimum number of inversions to make a digraph k-(arc-)-strong, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-054
Frédéric Havet and Stéphan Thomassé. Median orders of tournaments: A tool for the second neighborhood problem and sumner's conjecture. Journal of Graph Theory, 35(4):244-256, 2000.
https://doi.org/10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H
ANR Digraph Inversion Working Group. On the diameter of the inversion graph. Unpublished.
Vido Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.
Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972.
https://doi.org/10.1007/978-1-4684-2001-2_9
Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page 95-103, 2007.
https://doi.org/10.1145/1250790.1250806
Brendan D. McKay. The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs. Combinatorica, 10(4):367-377, 1990.
https://doi.org/10.1007/BF02128671
Crispin St J.A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. Canadian Journal of Mathematics, 12:555-567, 1960.
https://doi.org/10.4153/CJM-1960-049-6
Herbert E. Robbins. A theorem on graphs, with an application to a problem on traffic control. American Mathematical Monthly, 46(5):281-283, 1939.
https://doi.org/10.2307/2303897
Bhalchandra Thatte, Hamza Si Kaddour, and Maurice Pouzet. On the boolean dimension of a graph and other related parameters. Discrete Mathematics & Theoretical Computer Science, 23, 2022.
https://doi.org/10.46298/dmtcs.7437
Carsten Thomassen. Strongly 2-connected orientations of graphs. Journal of Combinatorial Theory, Series B, 110:67-78, 2015.
https://doi.org/10.1016/j.jctb.2014.07.004
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud