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
מספר עמודים12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2012
אירוע20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, סלובניה
משך הזמן: 10 ספט׳ 201212 ספט׳ 2012

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך7501 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס20th Annual European Symposium on Algorithms, ESA 2012

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Steiner forest orientation problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי