Min-sum 2-paths problems
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00087424" target="_blank" >RIV/00216224:14330/14:00087424 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-319-08001-7_1" target="_blank" >http://dx.doi.org/10.1007/978-3-319-08001-7_1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-08001-7_1" target="_blank" >10.1007/978-3-319-08001-7_1</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Min-sum 2-paths problems
Popis výsledku v původním jazyce
An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i in {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i in {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i in {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k >= 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum kedge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem.
Název v anglickém jazyce
Min-sum 2-paths problems
Popis výsledku anglicky
An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i in {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i in {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i in {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k >= 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum kedge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2014
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447
ISBN
9783319080000
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
11
Strana od-do
1-11
Název nakladatele
Springer
Místo vydání
Sophia Antipolis; France
Místo konání akce
Sophia Antipolis; France
Datum konání akce
1. 1. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—