Selecting vertex disjoint paths in plane graphs

Selecting vertex disjoint paths in plane graphs

0.00 Avg rating0 Votes
Article ID: iaor201526403
Volume: 66
Issue: 2
Start Page Number: 136
End Page Number: 144
Publication Date: Sep 2015
Journal: Networks
Authors: , , , , ,
Keywords: combinatorial optimization, heuristics
Abstract:

We study variants of the vertex disjoint paths problem in plane graphs where paths have to be selected from given sets of paths. We investigate the problem as a decision, maximization, and routing‐in‐rounds problem. Although all considered variants are NP‐hard in planar graphs, restrictions on the locations of the terminals on the outer face of the given planar embedding of the graph lead to polynomially solvable cases for the decision and maximization versions of the problem. For the routing‐in‐rounds problem, we obtain a p‐approximation algorithm, where p is the maximum number of alternative paths for a terminal pair, when restricting the locations of the terminals to the outer face such that they appear in a counterclockwise traversal of the boundary as a sequence s 1 , s 2 , … , s k , t π ( 1 ) , t π ( 2 ) , … , t π ( k ) for some permutation π .

Reviews

Required fields are marked *. Your email address will not be published.