The undirected two disjoint shortest paths problem

The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source–sink pairs $(s_i,t_i)$ asks if there exist $k$ pairwise edge- or vertex-disjoint shortest $s_i$–$t_i$-paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for $2$-DSPP on undirected graphs with non-negative edge lengths.     

Polynomial auction algorithms for shortest paths

In this paper we consider strongly polynomial variations of the auction algorithm for the single origin/many destinations shortest path problem. These variations are based on the idea of graph reduction, that is, deleting unnecessary arcs of the graph by using certain bounds naturally obtained in the course of the algorithm. We study the structure of the reduced graph and we exploit this structure to obtain algorithms withO (n min{m, n logn}) andO(n ²) running time. Our computational experiments show that these algorithms outperform their closest competitors on randomly generated dense all destinations problems, and on a broad variety of few destination problems.Research supported by NSF under Grant No. DDM-8903385, by the ARO under Grant DAAL03-86-K-0171, by a CNR-GNIM grant, and by a Fullbright grant     

Disjoint shortest paths in graphs

It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices.     

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.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

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.     

On finding shortest paths in nonnegative networks

A modification of Dantzig's algorithm for the all pairs shortest paths problem is given. The new algorithm applies only to graphs with nonnegative arc lengths. For an N-node complete graph it has a worst case running time of $\text{2}\text{3}\text{N}{}^3$ triple operations of the form D_ij: = min(D_ij, D_ik + D_kj) and N² log N other comparisons. This contrasts with a lower bound of N(N ? 1) (N ? 2) triples in any pure triple operation algorithm, and seems to be the first algorithm in which no operation need be repeated N³ times. Sparsity and some other conditions may also be utilized.     

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).     

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.     

Improved interface conditions for a non-overlapping domain decomposition of a non-convex polygonal domain

We propose a local improvement of domain decomposition methods which fits with the singularities occurring in the solutions of elliptic equations in polygonal domains. This short presentation focuses on a model elliptic problem with the decomposition of a non-convex polygonal domain into convex polygonal subdomains. After explaining the strategy and the theoretical design of adapted interface conditions at the corner, we present numerical experiments which show that these new interface conditions satisfy some optimality properties. To cite this article: C. Chniti et al., C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

An O(tmlogD) Algorithm for shortest paths

An implementation of Dykstra's shortest paths algorithm is proposed, which requires O(m log D) computations in worst case, where m denotes the number of arcs and D the length of the longest arc of the graphs considered. To this effect, a data structure called binary counting tree is introduced.     

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).     

A decomposition algorithm for shortest paths in a network with many strongly connected components

Summary This paper presents an algorithm for finding all shortest distances in a network with a large number of strongly connected components. If the network hasN nodes the number of computations required by this algorithm is asymptotically 1/6N(N–1) (N–2) tripel operations.

---

Zusammenfassung In der vorliegenden Arbeit wird ein Algorithmus zur Bestimmung der Längen aller kürzesten Wege in Netzwerken mit mehreren strengen Zusammenhangskomponenten entwickelt. Besitzt das NetzwerkN Knoten, so hat man bei diesem Algorithmus asymptotisch insgesamt 1/6N(N–1 (N–2) Additionen und ebenso viele Vergleiche durchzuführen.

     

Lower bounds for computing geometric spanners and approximate shortest paths

We consider the problems of constructing geometric spanners, possibly containing Steiner points, for a set of n input points in d-dimensional space , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles on the plane. The complexities of these problems are shown to be Ω(n log n) in the algebraic computation tree model. Since O(n log n)-time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor.     

Functions with a finite dirichlet integral in a domain with cusp points on the boundary

Let be a domain in ⁿ, n >2, the boundary of which has a cusp point, pointing inside or outside the domain. The purpose of the paper is to characterize the traces on of the elements of the space H¹() of functions with a finite Dirichlet integral. As a consequence one establishes the existence of a linear continuous extension operator H¹ () H¹(ⁿ) under the presence of an interior cusp point on . Theorems on domains with cusps are proved with the aid of results on cylindrical domains. In the space of functions with a finite Dirichlet integral in the exterior or the interior of the cylinder one introduces the norm, depending on a small parameter and generating a norm of the trace on as an element of the quotient space. The latter is placed in correspondence with an explicitly described norm of functions on the boundary, uniformly equivalent relative to . One constructs an operator of extension of functions from the exterior of the cylinder to Rⁿ, preserving H¹, whose norm is uniformly bounded relative to . For the optimal operator of extension from the inside of the cylinder one finds the asymptotic behavior of the norm as 0. From these results there follow similar theorems on functions with a finite Dirichlet integral inside and outside a thin closed tube (of width ).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 126, pp. 117–137, 1983.     

Rectilinear shortest paths in the presence of rectangular barriers

In this paper we address the following shortest-path problem. Given a point in the plane andn disjoint isothetic rectangles (barriers), we want to construct a shortestL ₁ path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are knowna priori) had been solved earlier inO(n ²) time. Our approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one ofx ory directions, we are able to apply a plane sweep technique to divide the plane intoO(n) rectangular regions. This leads to an algorithm whose complexity isO(n logn) preprocessing time,O(n) space, andO(logn+k) query time, wherek is the number of turns on the reported path. If only the length of the path is sought,O(logn) query time suffices. Furthermore, we show an (n logn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of our algorithm in this case.A preliminary version of this paper appeared in theProceedings of the First Symposium on Computational Geometry (1985).Supported in part by CNPq-Conselho Nacional de Desenvolvimento Científico e Tecnológico (Brazil).Supported in part by the National Science Foundation under Grants MCS 8420814 and ECS 8340031.     

Computing shortest paths in networks derived from recurrence relations

Dynamic programming formulations of optimization problems often call for the computation of shortest paths in networks derived from recurrence relations. These derived networks tend to be very large, but they are also very regular and lend themselves to the computation of nontrivial lower bounds on path lengths. In this tutorial paper, we describe unidirectional and bidirectional search procedures that make use of bounding information in computing shortest paths. When applied to many optimization problems, these shortest path algorithms capture the advantages of both dynamic programming and branch-and-bound.     

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

This paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion.The central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information.Our algorithms are randomized and have one-sided inverse polynomial error for query.