Arc-disjoint paths and trees in 2-regular digraphs
From MaRDI portal
Publication:2444565
DOI10.1016/j.dam.2013.04.018zbMath1285.05075arXiv1203.4705OpenAlexW2044338318MaRDI QIDQ2444565
Sven Simonsen, Jörgen Bang-Jensen
Publication date: 10 April 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1203.4705
spanning treemixed problempolynomial timeout-branchingconnected spanning subgraphin-branching2-regular digraph
Related Items (6)
Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Good orientations of unions of edge‐disjoint spanning trees ⋮ Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2 ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ Complexity of some arc-partition problems for digraphs ⋮ Non-separating spanning trees and out-branchings in digraphs of independence number 2
Cites Work
- Arc-disjoint spanning sub(di)graphs in digraphs
- A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
- Disjoint directed and undirected paths and cycles in digraphs
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the problem of finding disjoint cycles and dicycles in a digraph
- On the Problem of Decomposing a Graph into n Connected Factors
- Small degree out‐branchings
- Digraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Arc-disjoint paths and trees in 2-regular digraphs