Arc-disjoint paths and trees in 2-regular digraphs

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

zbMATH Keywords

spanning treemixed problempolynomial timeout-branchingconnected spanning subgraphin-branching2-regular digraph

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20)

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