Min-sum 2-paths problems (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00087424 |
|---|---|
| Název v anglickém jazyce | Min-sum 2-paths problems |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 3 |
| Počet domácích tvůrců | 1 |
| Výčet všech uvedených jednotlivých tvůrců | T. Fenner (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) O. Lachisch (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) Alexandru Popa (státní příslušnost: RO - Rumunsko, domácí tvůrce: A) |
| Popis výsledku v anglické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. |
| Klíčová slova oddělená středníkem | Additive polynomials; Edge-disjoint paths; K-paths; Min-sum; NP-hardness; Ordered pairs; Running time; Undirected graph |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1007/978-3-319-08001-7_1 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447 |
|---|---|
| ISBN | 9783319080000 |
| ISSN | 0302-9743 |
| 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 | 2014 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2016 |
| Specifikace | RIV/00216224:14330/14:00087424!RIV16-MSM-14330___ |
| Datum poslední aktualizace výsledku | 24.05.2016 |
| Kontrolní číslo | 191637631 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Podpora / návaznosti | Institucionální podpora na rozvoj výzkumné organizace |
|---|