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%2F21%3A10437395" target="_blank" >RIV/00216208:11320/21:10437395 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1cNq0XaSQN" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1cNq0XaSQN</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-020-00785-5" target="_blank" >10.1007/s00453-020-00785-5</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 roughly measures how many central nodes are visited by all shortest paths of a certain length. It has been shown that transportation networks, on which TSP and STP naturally occur for various applications in logistics, typically have a small highway dimension. While it was previously shown that these problems admit a quasi-polynomial time approximation scheme on graphs of constant highway dimension, we demonstrate that a significant improvement is possible in the special case when the highway dimension is 1. Specifically, we present a fully-polynomial time approximation scheme (FPTAS). We also prove that both TSP and STP are weakly NP-hard for these restricted graphs.

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 roughly measures how many central nodes are visited by all shortest paths of a certain length. It has been shown that transportation networks, on which TSP and STP naturally occur for various applications in logistics, typically have a small highway dimension. While it was previously shown that these problems admit a quasi-polynomial time approximation scheme on graphs of constant highway dimension, we demonstrate that a significant improvement is possible in the special case when the highway dimension is 1. Specifically, we present a fully-polynomial time approximation scheme (FPTAS). We also prove that both TSP and STP are weakly NP-hard for these restricted graphs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

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

Rok uplatnění

2021

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 periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

83

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

1352-1370

Kód UT WoS článku

000617411600001

EID výsledku v databázi Scopus

2-s2.0-85100986220