ﻻ يوجد ملخص باللغة العربية
We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M={(s_1,t_1),ldots,(s_k,t_k)}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Omega(log^{1/2-delta}n)$-approximation for any constant $delta$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Omega(sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $tilde O(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.
A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process g
Paths $P_1,ldots,P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph $G$
In the Disjoint Paths problem, the input is an undirected graph $G$ on $n$ vertices and a set of $k$ vertex pairs, ${s_i,t_i}_{i=1}^k$, and the task is to find $k$ pairwise vertex-disjoint paths connecting $s_i$ to $t_i$. The problem was shown to hav
We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88
The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how t