Edge-disjoint paths in digraphs with bounded independence number

DOI10.1016/J.JCTB.2014.07.002MaRDI QIDQ473097zbMATH OpenOpenAlexFDO

Authors Alexandra Fradkin, Paul Seymour

Publication date 21 November 2014

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

Full work available at URL https://doi.org/10.1016/j.jctb.2014.07.002

zbMATH Keywords

digraphspolynomial-time algorithmtournamentsindependence numberdisjoint pathslinking problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Disjoint paths in symmetric digraphs
• Induced disjoint paths problem in a planar digraph
• The Induced Disjoint Paths Problem
• On the disjoint paths problem
• Packing paths in digraphs

Cites work

• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Graph minors. XIII: The disjoint paths problem
• The directed subgraph homeomorphism problem
• Tournament immersion and cutwidth

Cited in

(24)

• LATIN 2004: Theoretical Informatics
• Few induced disjoint paths for \(H\)-free graphs
• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
• Quasi-transitive digraphs and their extensions
• On the Complexity of Singly Connected Vertex Deletion
• Non-separating spanning trees and out-branchings in digraphs of independence number 2
• Edge Disjoint Paths in Moderately Connected Graphs
• On the pathwidth of almost semicomplete digraphs
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• On width measures and topological problems on semi-complete digraphs
• Tournament pathwidth and topological containment
• scientific article; zbMATH DE number 50243 (Why is no real title available?)
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs
• Tournament immersion and cutwidth
• Disjoint paths in tournaments
• Tournaments and Semicomplete Digraphs
• Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs
• On the complexity of singly connected vertex deletion
• The condition of Beineke and Harary on edge-disjoint paths some of which are openly disjoint
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
• Digraphs of bounded width
• Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments
• Disjoint paths in unions of tournaments

This page was built for publication: Edge-disjoint paths in digraphs with bounded independence number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473097)