کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427856 686566 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding multiple induced disjoint paths in general graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Finding multiple induced disjoint paths in general graphs
چکیده انگلیسی

In an undirected graph, paths P1,P2,…,PkP1,P2,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E)G=(V,E), given k   node pairs {s1,t1},…,{sk,tk}{s1,t1},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k   and any ϵ>0ϵ>0, it is NP-hard to approximate MIDP within m1/2−ϵm1/2−ϵ, where m=|E|m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is m and an on-line algorithm which has a good lower bound.


► We investigate the Maximum Induced Disjoint Paths (MIDP) problem.
► We prove the hardness to approximate MIDP.
► We give two algorithms for MIDP: a greedy algorithm and an on-line algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 20, 31 October 2011, Pages 1022–1026
نویسندگان
, , ,