Publikation: Hierarchy of Transportation Network Parameters and Hardness Results
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
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(log2 |V|) it is NP-hard to approximate the k-Center problem within a factor less than 2.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BLUM, Johannes, 2019. Hierarchy of Transportation Network Parameters and Hardness Results. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Munich, Germany, 11. Sept. 2019 - 13. Sept. 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, 2019, 4. Leibniz International Proceedings in Informatics (LIPIcs). 148. eISSN 1868-8969. ISBN 978-3-95977-129-0. Available under: doi: 10.4230/LIPIcs.IPEC.2019.4BibTex
@inproceedings{Blum2019Hiera-48312,
year={2019},
doi={10.4230/LIPIcs.IPEC.2019.4},
title={Hierarchy of Transportation Network Parameters and Hardness Results},
number={148},
isbn={978-3-95977-129-0},
publisher={Schloss Dagstuhl, Leibniz-Zentrum für Informatik},
address={Wadern},
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}
}RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/48312">
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Blum, Johannes</dc:creator>
<dc:contributor>Blum, Johannes</dc:contributor>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-01-21T13:16:28Z</dcterms:available>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/48312"/>
<dc:language>eng</dc:language>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:issued>2019</dcterms:issued>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:title>Hierarchy of Transportation Network Parameters and Hardness Results</dcterms:title>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="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.</dcterms:abstract>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-01-21T13:16:28Z</dc:date>
</rdf:Description>
</rdf:RDF>
