Finding the K shortest hyperpaths using reoptimization

We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph. These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs.     

Algorithms for time-dependent bicriteria shortest path problems

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.     

Ranking paths in stochastic time-dependent networks

In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin–destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem.     

The shortest distance in random multi‐type intersection graphs

Using an associated branching process as the basis of our approximation, we show that typical inter‐point distances in a multi‐type random intersection graph have a defective distribution, which is well described by a mixture of translated and scaled Gumbel distributions, the missing mass corresponding to the event that the vertices are not in the same component of the graph. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 179–209, 2011     

Tight Hamilton cycles in random uniform hypergraphs

In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

The chromatic numbers of random hypergraphs

For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T₁,…,T_k such that |e∩T_i|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph H_r(n, p) for all possible values of γ and for all values of p down to p=Θ(n^−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks

We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic “time-adaptive” model and the more flexible “history-adaptive” one. We point out several properties of the sets of efficient solutions found under the two models. We also devise a method for finding supported history-adaptive solutions.     

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     

A compact hash function for paths in PERT networks

This paper presents a method of identifying all directed paths from the source to the sink (called ‘paths’ in this paper) in a directed acyclic network with one source and one sink. Let L be the set of all the paths in this network and N = |L|. A hash function H:L → {0, 1, …, N ? 1} is constructed having the following properties: it is one-to-one and onto, the algorithms to compute H and its inverse are linea in the number of arcs in the network, it has the smallest possible range and produces no collisions. All these properties make it a very useful hash function in writing computer programs which involve storing information about all paths in the network. The techniques described in this paper can be used to construct hash functions for walks in cyclic graphs. An application to simulation of stochastic networks is described and an illustrative example is included.     

Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015     

A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems

The purpose of this paper is to show how hard (equality constrained) knapsack problems may be converted into constrained shortest path problems. Several directions along which such a transformation might be exploited for algorithmic purposes are suggested.     

A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths

If each negative length arc of a digraphG is acyclic, i.e., does not belong to any cycle, then we show that the shortest paths from a given node to all other nodes can be computed inO(V ²) time, whereV is the number of nodes inG.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016     

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

Discrepancy of random graphs and hypergraphs

Answering in a strong form a question posed by Bollobás and Scott, in this paper we determine the discrepancy between two random k‐uniform hypergraphs, up to a constant factor depending solely on k. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 47, 147–162, 2015