A Parameterized View on Transportation Networks : Algorithms, Hierarchy, and Complexity

Lade...
Vorschaubild
Dateien
Blum_2-1u8jlxhc3ko79.pdf
Blum_2-1u8jlxhc3ko79.pdfGröße: 5.29 MBDownloads: 134
Datum
2023
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

Many everyday optimization problems arise in transportation networks, such as vehicle and pedestrian navigation, truck route planning, or facility location problems in logistics. To solve such problems, efficient algorithms are required. To that end, the transportation network is usually modeled as a graph, where the vertices represent locations (e.g., road intersections or train stations) and the edges represent connections between them. To develop efficient algorithms for the corresponding graph problems, it is in many cases beneficial to exploit certain properties of the resulting graph. This motivated the development of several models for graphs representing transportation networks, e.g., the graph parameters highway dimension and skeleton dimension, which capture the structure of shortest paths in a graph, or bounded growth graphs.

In this work, we consider different parameters that are commonly used to model transportation networks. We utilize them to develop efficient algorithms, study the relationships between different parameters, and demonstrate the limitations of these models.

In the first part, we consider the shortest path problem. Three of the most successful algorithms for this problem in transportation networks are Contraction Hierarchies, Hub Labeling, and Transit Node Routing. First, we investigate these algorithms on bounded growth graphs. A graph has bounded growth if there is a constant g such that for any vertex u and any r>0, the number of vertices at distance r from u is at most g⋅r. We improve upon a previous result of Funke and Storandt [ISAAC '15] and show that in this model, it is possible to achieve a space consumption of O(n log D) for Contraction Hierarchies on unweighted graphs, where D denotes the diameter of the graph. Furthermore, we analyze the search space sizes and space consumption of Hub Labeling and Transit Node Routing on bounded growth graphs, and also consider weighted graphs.

We then study variants of Hub Labeling and Contraction Hierarchies, and show that we can lower bound the size of their respective search spaces in terms of the size of minimum balanced separators. This allows us to develop a O(log2 n)-approximation algorithm for the search spaces sizes.

In the second part, we consider various graph parameters, including highway dimension, skeleton dimension, and bounded growth number. We study the relationships between different parameters, which allows us to incorporate them into a hierarchy.

The third part is concerned with the computational complexity of two graph problems. We show that it is NP-hard to compute the highway dimension of a graph according to the recent definition of Abraham et al. [J. ACM '16]. Moreover, we develop a polynomial time algorithm to compute the highway dimension of a tree.

Finally, we consider the k-Center problem. First, we show that for any ϵ>0 it is NP-hard to compute a (2-ϵ)-approximation if the given graph has a skeleton dimension of κ ∈ O(log2 n). Finally, we study the fixed-parameter tractability of k-Center and show that the problem is W[1]-hard if the parameter combines the number of centers, the highway dimension, the skeleton dimension and the pathwidth, even if the given graph is planar and has constant doubling dimension.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
graph parameter, transportation network, skeleton dimension, highway dimension, bounded growth, hub labeling, contraction hierarchy, route planning, k-center
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BLUM, Johannes, 2023. A Parameterized View on Transportation Networks : Algorithms, Hierarchy, and Complexity [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Blum2023Param-59922,
  year={2023},
  title={A Parameterized View on Transportation Networks : Algorithms, Hierarchy, and Complexity},
  author={Blum, Johannes},
  address={Konstanz},
  school={Universität Konstanz}
}
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/59922">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59922/3/Blum_2-1u8jlxhc3ko79.pdf"/>
    <dc:contributor>Blum, Johannes</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>terms-of-use</dc:rights>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">&lt;p&gt;Many everyday optimization problems arise in transportation networks, such as vehicle and pedestrian navigation, truck route planning, or facility location problems in logistics. To solve such problems, efficient algorithms are required. To that end, the transportation network is usually modeled as a graph, where the vertices represent locations (e.g., road intersections or train stations) and the edges represent connections between them. To develop efficient algorithms for the corresponding graph problems, it is in many cases beneficial to exploit certain properties of the resulting graph. This motivated the development of several models for graphs representing transportation networks, e.g., the graph parameters highway dimension and skeleton dimension, which capture the structure of shortest paths in a graph, or bounded growth graphs.&lt;/p&gt; &lt;p&gt;In this work, we consider different parameters that are commonly used to model transportation networks. We utilize them to develop efficient algorithms, study the relationships between different parameters, and demonstrate the limitations of these models.&lt;/p&gt; &lt;p&gt;In the first part, we consider the shortest path problem. Three of the most successful algorithms for this problem in transportation networks are Contraction Hierarchies, Hub Labeling, and Transit Node Routing. First, we investigate these algorithms on bounded growth graphs. A graph has bounded growth if there is a constant g such that for any vertex u and any r&gt;0, the number of vertices at distance r from u is at most g⋅r. We improve upon a previous result of Funke and Storandt [ISAAC '15] and show that in this model, it is possible to achieve a space consumption of O(n log D) for Contraction Hierarchies on unweighted graphs, where D denotes the diameter of the graph. Furthermore, we analyze the search space sizes and space consumption of Hub Labeling and Transit Node Routing on bounded growth graphs, and also consider weighted graphs.&lt;/p&gt; &lt;p&gt;We then study variants of Hub Labeling and Contraction Hierarchies, and show that we can lower bound the size of their respective search spaces in terms of the size of minimum balanced separators. This allows us to develop a O(log&lt;sup&gt;2&lt;/sup&gt; n)-approximation algorithm for the search spaces sizes.&lt;/p&gt; &lt;p&gt;In the second part, we consider various graph parameters, including highway dimension, skeleton dimension, and bounded growth number. We study the relationships between different parameters, which allows us to incorporate them into a hierarchy.&lt;/p&gt; &lt;p&gt;The third part is concerned with the computational complexity of two graph problems. We show that it is NP-hard to compute the highway dimension of a graph according to the recent definition of Abraham et al. [J. ACM '16]. Moreover, we develop a polynomial time algorithm to compute the highway dimension of a tree.&lt;/p&gt;&lt;p&gt;Finally, we consider the k-Center problem. First, we show that for any ϵ&gt;0 it is NP-hard to compute a (2-ϵ)-approximation if the given graph has a skeleton dimension of κ ∈ O(log&lt;sup&gt;2&lt;/sup&gt; n). Finally, we study the fixed-parameter tractability of k-Center and show that the problem is W[1]-hard if the parameter combines the number of centers, the highway dimension, the skeleton dimension and the pathwidth, even if the given graph is planar and has constant doubling dimension.&lt;/p&gt;</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59922"/>
    <dcterms:issued>2023</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-25T09:36:56Z</dc:date>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-25T09:36:56Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Blum, Johannes</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59922/3/Blum_2-1u8jlxhc3ko79.pdf"/>
    <dcterms:title>A Parameterized View on Transportation Networks : Algorithms, Hierarchy, and Complexity</dcterms:title>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
May 25, 2022
Hochschulschriftenvermerk
Konstanz, Univ., Diss., 2022
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen