Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

Computing homotopic shortest paths efficiently

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(k_out+k_inlogn+n(logn)^1+ε). Here k_in is the number of edges in all the paths of Π, and k_out is the number of edges in the output paths.     

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Parallel asynchronous label-correcting methods for shortest paths

We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

Algorithms for shortest paths and d-cycle problems

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n²m) and O(n^2d−1m²) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^2d−1+n²m+n³logn).     

Bottleneck shortest paths on a partially ordered scale

In bottleneck combinatorial problems, admissible solutions are compared with respect to their maximal elements. In such problems, one may work with an ordinal evaluation scale instead of a numerical scale. We consider here a generalization of this problem in which one only has a partially ordered scale (instead of a completely ordered scale). After the introduction of a mappimax comparison operator between sets of evaluations (which boils down to the classical operator when the order is complete), we establish computational complexity results for this variation of the shortest path problem. Finally, we formulate our problem as an algebraic shortest path problem and suggest adequate algorithms to solve it in the subsequent semiring.Received: June 2002, Revised: March 2003, AMS classification: 05C50, 16Y60, 90B06Olivier Spanjaard: Corresponding author.     

Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.     

Solving the shortest path tour problem

In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.     

A new algorithm for reoptimizing shortest paths when the arc costs change

We propose the first algorithmic approach which reoptimizes the shortest paths when any subset of arcs of the input graph is affected by a change of the costs, which can be either lower or higher than the old ones. This situation is more general than the ones addressed in the literature so far. We analyze the worst-case time complexity of the algorithm as a function of both the input size and the overall cost perturbation, and discuss cases for which the proposed reoptimization method theoretically outperforms the approach of applying a standard shortest path algorithm after the change of the arc costs.     

New models for shortest path problem with fuzzy arc lengths

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.     

Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves

We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space without planar unfolding. The concept of a funnel associated with a common edge along a sequence of triangles is introduced, that is similar to Lee and Preparata’s one in a simple polygon. The sequence of funnels associated with all common edges of the sequence is constructed and then the shortest path is determined by cusps of these funnels. Such funnels are determined iteratively to their associated edges by the Method of Orienting Curves, which was introduced by Phu [Ein konstruktives Lösungsverfahren für das Problem des Inpolygons kleinsten Umfangs von J. Steiner. Optimization. 1987;18:349–359]. The method consists of the concepts of final curves and orienting curves (the special cases of straightest geodesics). We then show that the shortest path from the cusp of a given funnel to the direct destination in the processed region of the funnel is determined by parts of orienting curves and a final curve. A numerical example for finding the shortest path joining two points in the sequence of triangles is presented and visualized by JavaView software.     

An aggregate label setting policy for the multi-objective shortest path problem

We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.     

The robust shortest path problem in series-parallel multidigraphs with interval data

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.