KOPS - The Institutional Repository of the University of Konstanz
# Hierarchy of Transportation Network Parameters and Hardness Results

Type of Publication: | Contribution to a conference collection |

Publication status: | Published |

Author: | Blum, Johannes |

Year of publication: | 2019 |

Conference: | 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Sep 11, 2019 - Sep 13, 2019, Munich, Germany |

Published in: | 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) / Jansen, Bart M. P.; Telle, Jan Arne (ed.). - Wadern : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 148). - 4. - eISSN 1868-8969. - ISBN 978-3-95977-129-0 |

DOI (citable link): | https://dx.doi.org/10.4230/LIPIcs.IPEC.2019.4 |

Summary: |
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
^{2} |V|) it is NP-hard to approximate the k-Center problem within a factor less than 2. |

Subject (DDC): | 004 Computer Science |

Keywords: | Graph Parameters, Skeleton Dimension, Highway Dimension, k-Center |

Bibliography of Konstanz: | Yes |

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} }