Finding multiple induced disjoint paths in general graphs

DOI10.1016/j.ipl.2011.07.016zbMath1260.68307OpenAlexW2008183483MaRDI QIDQ1944193

Hong Gao, Jian-Zhong Li, Ke-Jia Zhang

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.07.016

zbMATH Keywords

graphapproximation algorithminduced disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Induced disjoint paths problem in a planar digraph
• On the disjoint paths problem
• Edge-disjoint paths in Planar graphs with constant congestion
• The Induced Disjoint Paths Problem
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding multiple induced disjoint paths in general graphs