Arc-Disjoint Paths in Decomposable Digraphs

DOI10.1002/jgt.21775zbMath1302.05063OpenAlexW2146463098MaRDI QIDQ2922218

Alessandro Maddaloni, Jörgen Bang-Jensen

Publication date: 9 October 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21775

zbMATH Keywords

locally semicomplete digraphquasi-transitive digraphdecomposable digraphcut-widtharc-disjoint pathsmodular partitionweak linkages

Mathematics Subject Classification ID

Graph polynomials (05C31) Directed graphs (digraphs), tournaments (05C20)

Related Items (14)

The knapsack problem with special neighbor constraints ⋮ Computing directed Steiner path covers ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Solutions for subset sum problems with special digraph constraints ⋮ How to compute digraph width measures on directed co-graphs ⋮ Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract) ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Oriented coloring on recursively defined digraphs ⋮ On characterizations for subclasses of directed co-graphs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Quasi-Transitive Digraphs and Their Extensions ⋮ Miscellaneous Digraph Classes ⋮ Disjoint Paths in Decomposable Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• The directed subgraph homeomorphism problem
• Fully dynamic recognition algorithm and certificate for directed cographs
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Quasi‐transitive digraphs
• Digraphs

This page was built for publication: Arc-Disjoint Paths in Decomposable Digraphs