License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2019.4
URN: urn:nbn:de:0030-drops-114656
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11465/
Go to the corresponding LIPIcs Volume Portal

Blum, Johannes

Hierarchy of Transportation Network Parameters and Hardness Results

pdf-format:
LIPIcs-IPEC-2019-4.pdf (0.5 MB)

Abstract

The graph parameters highway dimension and skeleton dimension were introduced to capture the properties of transportation networks. As many important optimization problems like Travelling Salesperson, Steiner Tree or k-Center arise in such networks, it is worthwhile to study them on graphs of bounded highway or skeleton dimension.
We investigate the relationships between mentioned parameters and how they are related to other important graph parameters that have been applied successfully to various optimization problems. We show that the skeleton dimension is incomparable to any of the parameters distance to linear forest, bandwidth, treewidth and highway dimension and hence, it is worthwhile to study mentioned problems also on graphs of bounded skeleton dimension. Moreover, we prove that the skeleton dimension is upper bounded by the max leaf number and that for any graph on at least three vertices there are edge weights such that both parameters are equal.
Then we show that computing the highway dimension according to most recent definition is NP-hard, which answers an open question stated by Feldmann et al. [Andreas Emil Feldmann et al., 2015]. Finally we prove that on graphs G=(V,E) of skeleton dimension O(log^2 |V|) it is NP-hard to approximate the k-Center problem within a factor less than 2.

BibTeX - Entry

@InProceedings{blum:LIPIcs:2019:11465,
  author =	{Johannes Blum},
  title =	{{Hierarchy of Transportation Network Parameters and Hardness Results}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Bart M. P. Jansen and Jan Arne Telle},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11465},
  URN =		{urn:nbn:de:0030-drops-114656},
  doi =		{10.4230/LIPIcs.IPEC.2019.4},
  annote =	{Keywords: Graph Parameters, Skeleton Dimension, Highway Dimension, k-Center}
}

Keywords: Graph Parameters, Skeleton Dimension, Highway Dimension, k-Center
Collection: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI