Steiner forest orientation problems

Marek Cygan, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u,v) ∈ P: D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V,E) with edge-costs and a set P ⊆ V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multi-collection of ordered node pairs P on V. The goal is to find an orientation D of G such that |P[D]| is maximum. Generalizing the result of Arkin and Hassin [DAM'02] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in n O(|P|) time whether G has an orientation D with P[D] = P (for undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs). For undirected graphs, we will show that one can decide whether G admits an orientation D with |P[D]| ≥ k in O(n + m) + 2 O(k·loglogk) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [AMB'11]. We also show that Maximum Pairs Orientation admits ratio O(log|P|/loglog|P|), which is better than the ratio O(logn/loglogn) of Gamzu et al. [WABI'10] when |P| < n. Finally, we show that the following node-connectivity problem can be solved in polynomial time: given a graph G = (V,E) with edge-costs, s,t ∈ V, and an integer ℓ, find a min-cost subgraph H of G with an orientation D such that D contains ℓ internally-disjoint st-paths, and ℓ internally-disjoint ts-paths.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
الصفحات361-372
عدد الصفحات12
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2012
الحدث20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, سلوفينيا
المدة: ١٠ سبتمبر ٢٠١٢١٢ سبتمبر ٢٠١٢

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت7501 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference20th Annual European Symposium on Algorithms, ESA 2012
الدولة/الإقليمسلوفينيا
المدينةLjubljana
المدة١٠/٠٩/١٢١٢/٠٩/١٢

بصمة

أدرس بدقة موضوعات البحث “Steiner forest orientation problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا