Hierarchy of Transportation Network Parameters and Hardness Results

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BLUM, Johannes, 2019. Hierarchy of Transportation Network Parameters and Hardness Results. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Munich, Germany, Sep 11, 2019 - Sep 13, 2019. In: JANSEN, Bart M. P., ed., Jan Arne TELLE, ed.. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Wadern:Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 4. eISSN 1868-8969. ISBN 978-3-95977-129-0. Available under: doi: 10.4230/LIPIcs.IPEC.2019.4

@inproceedings{Blum2019Hiera-48312, title={Hierarchy of Transportation Network Parameters and Hardness Results}, year={2019}, doi={10.4230/LIPIcs.IPEC.2019.4}, number={148}, isbn={978-3-95977-129-0}, address={Wadern}, publisher={Schloss Dagstuhl, Leibniz-Zentrum für Informatik}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, booktitle={14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, editor={Jansen, Bart M. P. and Telle, Jan Arne}, author={Blum, Johannes}, note={Article Number: 4} }

2019 Hierarchy of Transportation Network Parameters and Hardness Results Blum, Johannes 2020-01-21T13:16:28Z Blum, Johannes eng 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. [18]. Finally we prove that on graphs G = (V,E) of skeleton dimension O(log<sup>2</sup> |V|) it is NP-hard to approximate the k-Center problem within a factor less than 2. 2020-01-21T13:16:28Z

This item appears in the following Collection(s)

Search KOPS


Browse

My Account