Travelling on Graphs with Small Highway Dimension

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404755" target="_blank" >RIV/00216208:11320/19:10404755 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-30786-8_14" target="_blank" >https://doi.org/10.1007/978-3-030-30786-8_14</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-30786-8_14" target="_blank" >10.1007/978-3-030-30786-8_14</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Travelling on Graphs with Small Highway Dimension

Popis výsledku v původním jazyce

We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] as a model for transportation networks, on which TSP and STP naturally occur for various applications in logistics. It was previously shown [Feldmann et al. ICALP 2015] that these problems admit a quasi-polynomial time approximation scheme (QPTAS) on graphs of constant highway dimension. We demonstrate that a significant improvement is possible in the special case when the highway dimension is 1, for which we present a fully-polynomial time approximation scheme (FPTAS). We also prove that STP is weakly

Název v anglickém jazyce

Travelling on Graphs with Small Highway Dimension

Popis výsledku anglicky

We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] as a model for transportation networks, on which TSP and STP naturally occur for various applications in logistics. It was previously shown [Feldmann et al. ICALP 2015] that these problems admit a quasi-polynomial time approximation scheme (QPTAS) on graphs of constant highway dimension. We demonstrate that a significant improvement is possible in the special case when the highway dimension is 1, for which we present a fully-polynomial time approximation scheme (FPTAS). We also prove that STP is weakly

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Optimalizace sítí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

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ů

Název statě ve sborníku

Graph-Theoretic Concepts in Computer Science; 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers

ISBN

978-3-030-30785-1

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

175-189

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Vall de Núria, Spain

Datum konání akce

19. 6. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—