Arc-disjoint spanning sub(di)graphs in digraphs

DOI10.1016/j.tcs.2012.03.003zbMath1247.68096MaRDI QIDQ441857

Anders Yeo, Jörgen Bang-Jensen

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.003

zbMATH Keywords

NP-completeness; branchings; spanning trees; arc-disjoint subdigraphs; paths and cycles

Mathematics Subject Classification ID

05C38: Paths and cycles

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C20: Directed graphs (digraphs), tournaments

Related Items

Good orientations of unions of edge‐disjoint spanning trees, Parameterized algorithms for non-separating trees and branchings in digraphs, Antistrong digraphs, On the tractability of some natural packing, covering and partitioning problems, Complexity of some arc-partition problems for digraphs, Non-separating spanning trees and out-branchings in digraphs of independence number 2, Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs, (Arc-)disjoint flows in networks, Arc-disjoint paths and trees in 2-regular digraphs, Finding good 2-partitions of digraphs. II. Enumerable properties, The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties, Arc-Disjoint Directed and Undirected Cycles in Digraphs

Cites Work

• Unnamed Item
• Vertex-disjoint directed and undirected cycles in general digraphs
• Decomposing locally semicomplete digraphs into strong spanning subdigraphs
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
• Disjoint directed and undirected paths and cycles in digraphs
• Matroid theory and its applications in electric network theory and in statics
• On two minimax theorems in graph
• On the problem of finding disjoint cycles and dicycles in a digraph
• Disjoint sub(di)graphs in digraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Digraphs