Edge-disjoint in- and out-branchings in tournaments and related path problems

DOI10.1016/0095-8956(91)90002-2zbMath0659.05052OpenAlexW2038926198MaRDI QIDQ1112061

Jörgen Bang-Jensen

Publication date: 1991

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(91)90002-2

zbMATH Keywords

NP-completenesstournamentpolynomial algorithmsbranchingsedge-disjoint pathssemicomplete digraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (26)

The smallest number of vertices in a 2-arc-strong digraph without pair of arc-disjoint in- and out-branchings ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Arc-Disjoint Paths in Decomposable Digraphs ⋮ Good orientations of unions of edge‐disjoint spanning trees ⋮ Quasi‐transitive digraphs ⋮ Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2 ⋮ Good acyclic orientations of 4‐regular 4‐connected graphs ⋮ Precedence-constrained arborescences ⋮ Decomposing locally semicomplete digraphs into strong spanning subdigraphs ⋮ Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs ⋮ Arc-disjoint paths and trees in 2-regular digraphs ⋮ Edge-disjoint paths in digraphs with bounded independence number ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph ⋮ The minimum spanning strong subdigraph problem is fixed parameter tractable ⋮ On unitarity of spherical representations ⋮ Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Complexity of some arc-partition problems for digraphs ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Linkages in locally semicomplete digraphs and quasi-transitive digraphs ⋮ Tournaments and Semicomplete Digraphs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Quasi-Transitive Digraphs and Their Extensions ⋮ Smallest number of vertices in a 2-arc-strong digraph without good pairs ⋮ Non-separating spanning trees and out-branchings in digraphs of independence number 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Hamiltonian-connected tournaments
• On two minimax theorems in graph
• The maximum number of arc-disjoint arborescences in a tournament
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Paths, Trees, and Flowers

This page was built for publication: Edge-disjoint in- and out-branchings in tournaments and related path problems