An improved algorithm for the half-disjoint paths problem

DOI10.1137/100808812MaRDI QIDQ3225124zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100808812

zbMATH Keywords

disjoint pathsgrid-like minorhalf-integral packingtree width

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Improved algorithm for the half-disjoint paths problem
• scientific article; zbMATH DE number 1775441
• On the complexity of the disjoint paths problem
• On the disjoint paths problem
• A nearly linear time algorithm for the half integral parity disjoint paths packing problem

Cited in

(11)

• On the disjoint paths problem
• Graph minors and parameterized algorithm design
• Improved algorithm for the half-disjoint paths problem
• Improved Algorithms for the 2-Vertex Disjoint Paths Problem
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• A nearly linear time algorithm for the half integral parity disjoint paths packing problem
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Half-integral linkages in highly connected directed graphs
• Faster algorithms for half-integral T-path packing
• Combing a Linkage in an Annulus

This page was built for publication: An improved algorithm for the half-disjoint paths problem

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