Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths e.g. road or grid networks an important challenge. The most successful techniques fast query answering rely on preprocessing. But of these it not fully understood why they perform so remarkably well and theoretical justification the empirical results missing. An attempt to explain excellent practical performance preprocessing based (as transit nodes,...

The graph parameters highway dimension and skeleton 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 study them on graphs bounded dimension. We investigate relationships between mentioned how they are related other that have been applied successfully various problems. We show incomparable any distance linear forest, bandwidth,...

Resource demands are crucial parameters for modeling and predicting the performance of software systems. Currently, resource demand estimators usually executed once system analysis. However, monitored system, as well itself, subject to constant change in runtime environments. These changes additionally impact applicability, required parametrization resulting accuracy individual estimation approaches. Over time, this leads invalid or outdated estimates, which turn negatively influence...

In this paper, we thoroughly analyze the scaling behavior of several state-of-the-art route planning techniques for road networks, all which rely on preprocessing. One goal is to determine technique most suitable be used huge networks. To able conduct scalability studies in a clean way, first describe new kind network generator that allows produce networks even larger than our planet with similar properties as real We then carefully implement preprocessing-based techniques, contraction...

Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing search space size bidirectional Dijkstra run. To explain practical success CH, several theoretical upper bounds for maximum were derived previous work. For example, it was shown minor-closed graph families sizes 𝒪(√n) can be achieved (with n denoting number nodes graph), and 𝒪(h log D) graphs highway dimension h diameter D. In this paper,...

Abstract Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks an important challenge. The most successful techniques fast query answering rely on preprocessing. However, of these it not fully understood why they perform so remarkably well, and theoretical justification the empirical results missing. An attempt to explain excellent practical performance preprocessing based...

Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed G (having directed and undirected edges) set T of k terminal pairs G, there an orientation the edges such that path for every pair ? This problem was shown to be NP -complete Arkin Hassin [1] later W [1]-hard Pilipczuk Wahlström [7], parametrized k. On other hand, XP algorithm Cygan et al. [3] polynomial time graphs without Megiddo [5]. Chitnis Feldmann [2]...

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system $(V,\mathcal{F},\mathcal{B})$ with two families $\mathcal{F},\mathcal{B}$ of subsets $V$. The task is to find hitting for $\mathcal{F}$ that minimizes maximum number elements in any sets $\mathcal{B}$. Our focus on determining complexity some special cases Sparse-HS respect sparseness $k$, which optimum For Vertex Cover (Sparse-VC) $V$ by vertex graph, and its edge set. prove NP-hardness $k\geq 2$...

Abstract We study the k -Center problem, where input is a graph $$G=(V,E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> with positive edge weights and an integer , goal to select center vertices $$C \subseteq V$$ <mml:mi>C</mml:mi> <mml:mo>⊆</mml:mo> such that maximum distance from any vertex closest minimized....

Several algorithms for path planning in grid networks rely on graph decomposition to reduce the search space size; either by constructing a data structure components, or using component information A* guidance. The focus is usually obtaining components of roughly equal size with few boundary nodes each. In this paper, we consider problem splitting into convex components. A characterized property that all pairs its members, shortest between them also contained it. Thus, given source node,...

The graph parameters highway dimension and skeleton 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 study them on graphs bounded dimension. We investigate relationships between mentioned how they are related other that have been applied successfully various problems. show incomparable any distance linear forest, bandwidth, treewidth...

In the $k$-Center problem, we are given a graph $G=(V,E)$ with positive edge weights and an integer $k$ goal is to select center vertices $C \subseteq V$ such that maximum distance from any vertex closest minimized. On general graphs, problem NP-hard cannot be approximated within factor less than $2$. Typical applications of can found in logistics or urban planning hence, it natural study on transportation networks. Such networks often characterized as graphs (almost) planar have low...

Hub Labeling (HL) is one of the state-of-the-art preprocessing-based techniques for route planning in road networks. It a special incarnation distance labeling, and it well-studied both theory practice. The core concept HL to associate label with each vertex, which consists subset all vertices respective shortest path information, such that between any two can be derived from considering intersection their labels. provides excellent query times but requires time-consuming preprocessing...