Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
From MaRDI portal
Publication:6093584
DOI10.1016/j.tcs.2023.114097arXiv2303.03296OpenAlexW4385336697MaRDI QIDQ6093584
Matthias Kriesell, Jörgen Bang-Jensen, Florian Hoersch
Publication date: 7 September 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2303.03296
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strongly 2-connected orientations of graphs
- On the orientation of graphs and hypergraphs
- Making a tournament \(k\)-arc-strong by reversing or deorienting arcs.
- Some APX-completeness results for cubic graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimal edge-coverings of pairs of sets
- Checking the admissibility of odd-vertex pairings is hard
- On Frank's conjecture on \(k\)-connected orientations
- Simultaneous well-balanced orientations of graphs
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- A Minimax Theorem for Directed Graphs
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- Digraphs
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Combinatorial optimization. Theory and algorithms
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
This page was built for publication: Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
