Edge-disjoint paths in digraphs with bounded independence number

DOI10.1016/J.JCTB.2014.07.002zbMATH Open1302.05067OpenAlexW1988500978MaRDI QIDQ473097FDOQ473097

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

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

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)

Cites Work

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

Cited In (24)

• Few induced disjoint paths for \(H\)-free graphs
• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
• Digraphs of Bounded Width
• On the Complexity of Singly Connected Vertex Deletion
• Edge Disjoint Paths in Moderately Connected Graphs
• Non-separating spanning trees and out-branchings in digraphs of independence number 2
• 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
• Quasi-Transitive Digraphs and Their Extensions
• On width measures and topological problems on semi-complete digraphs
• Tournament pathwidth and topological containment
• Title not available (Why is that?)
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs
• Tournament immersion and cutwidth
• Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs
• Tournaments and Semicomplete Digraphs
• Disjoint paths in tournaments
• On the complexity of singly connected vertex deletion
• On the Pathwidth of Almost Semicomplete Digraphs
• 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
• Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments
• Disjoint paths in unions of tournaments
• LATIN 2004: Theoretical Informatics

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)