Computing shortest paths for any number of hops

In this paper, we introduce and investigate a "new" path optimization problem that we denote the all hops optimal path (AHOP) problem. The problem involves identifying, for all hop counts, the optimal, i.e., minimum weight, path(s) between a given source and destination(s). The AHOP problem arises naturally in the context of quality-of-service (QoS) routing in networks, where routes (paths) need to be computed that provide services guarantees, e.g., delay or bandwidth, at the minimum possible "cost" (amount of resources required) to the network. Because service guarantees are typically provided through some form of resource allocation on the path (links) computed for a new request, the hop count, which captures the number of links over which resources are allocated, is a commonly used cost measure. As a result, a standard approach for determining the cheapest path available that meets a desired level of service guarantees is to compute a minimum hop shortest (optimal) path. Furthermore, for efficiency purposes, it is desirable to precompute such optimal minimum hop paths for all possible service requests. Providing this information gives rise to solving the AHOP problem. The paper's contributions are to investigate the computational complexity of solving the AHOP problem for two of the most prevalent cost functions (path weights) in networks, namely, additive and bottleneck weights. In particular, we establish that a solution based on the Bellman-Ford algorithm is optimal for additive weights, but show that this does not hold for bottleneck weights for which a lower complexity solution exists.     

Alternative shortest paths in n-cubes

Explicit expressions are given for the number of shortest paths between any two vertices in an n-cube, each path being otherwise vertex disjoint from any specified shortest path between the same pair of vertices, and for the probability of randomly selecting one of these alternative paths     

DT-MRI fiber tracking: a shortest paths approach

We derive a new fiber tracking algorithm for DT-MRI that parts with the locally “greedy” paradigm intrinsic to conventional tracking algorithms. We demonstrate the ability to precisely reconstruct a diverse range of fiber trajectories in authentic and computer-generated DT-MRI data, for which well-known conventional tracking algorithms are shown to fail. Our approach is to pose fiber tracking as a problem in computing shortest paths in a weighted digraph. Voxels serve as vertices, and edges are included between neighboring voxels. We assign probabilities (weights) to edges using a Bayesian framework. Higher probabilities are assigned to edges that are aligned with fiber trajectories in their close proximity. We compute optimal paths of maximum probability using computationally scalable shortest path algorithms. The salient features of our approach are: global optimality—unlike conventional tracking algorithms, local errors do not accumulate and one “wrong-turn” does not spell disaster; a target point is specified a priori; precise reconstruction is demonstrated for extremely low signal-to-noise ratio; impartiality to which of two endpoints is used as a seed; and, faster computation times than conventional all-paths tracking. We can use our new tracking algorithm in either a single-path tracking mode (deterministic tracking) or an all-paths tracking mode (probabilistic tracking).      

Finding spatio-temporal salient paths for video objects discovery

Many videos capture and follow salient objects in a scene. Detecting such salient objects is thus of great interests to video analytics and search. However, the discovery of salient objects in an unsupervised way is a challenging problem as there is no prior knowledge of the salient objects provided. Different from existing salient object detection methods, we propose to detect and track salient object by finding a spatio-temporal path which has the largest accumulated saliency density in the video. Inspired by the observation that salient video objects usually appear in consecutive frames, we leverage the motion coherence of videos into the path discovery and make the salient object detection more robust. Without any prior knowledge of the salient objects, our method can detect salient objects of various shapes and sizes, and is able to handle noisy saliency maps and moving cameras. Experimental results on two public datasets validate the effectiveness of the proposed method in both qualitative and quantitative terms. Comparisons with the state-of-the-art methods further demonstrate the superiority of our method on salient object detection in videos.     

Finding multi-constrained feasible paths by using depth-first search

An extended depth-first-search (EDFS) algorithm is proposed to solve the multi-constrained path (MCP) problem in Quality-of-Service (QoS) routing, which is NP-Complete when the number of independent routing constraints is more than one. EDFS solves the general k-constrained MCP problem with pseudo-polynomial time complexity O(m ² · EN + N ²), where m is the maximum number of non-dominated paths maintained for each destination, E and N are the number of links and nodes of a graph, respectively. This is achieved by deducing potential feasible paths from knowledge of previous explorations, without re-exploring finished nodes and their descendants in the process of the DFS search. One unique property of EDFS is that the tighter the constraints are, the better the performance it can achieve, w.r.t. both time complexity and routing success ratio. This is valuable to highly dynamic environment such as wireless ad hoc networks in which network topology and link state keep changing, and real-time or multimedia applications that have stringent service requirements. EDFS is an independent feasible path searching algorithm and decoupled from the underlying routing protocol, and as such can work together with either proactive or on-demand ad hoc routing protocols as long as they can provide sufficient network state information to each source node. Analysis and extensive simulation are conducted to study the performance of EDFS in finding feasible paths that satisfy multiple QoS constraints. The main results show that EDFS is insensitive to the number of constraints, and outperforms other popular MCP algorithms when the routing constraints are tight or moderate. The performance of EDFS is comparable with that of the other algorithms when the constraints are loose. This work was supported in part by the National Science Foundation under Grant CNS-0435522, by the UCOP CLC under grant SC-05-33 and by the Baskin Chair of Computer Engineering at University of California, Santa Cruz. Zhenjiang Li received the B.S. and M.S. degrees in electronic engineering from University of Science and Technology of China (USTC), Hefei, China, in 1998 and 2001, respectively. Since 2001, he has been a PhD student in the computer communication research group (CCRG) of the computer engineering department, University of California, Santa Cruz, U.S.A. His research interests include secure routing, constrained path selection, routing optimization and quality-of-service (QoS) provisioning in computer networks. He is a student member of the IEEE. J. J. Garcia-Luna-Aceves received the B.S. degree in electrical engineering from the Universidad Iberoamericana in Mexico City, Mexico in 1977, and the M.S. and Ph.D. degrees in electrical engineering from the University of Hawaii, Honolulu, HI, in 1980 and 1983, respectively. He holds the Jack Baskin Chair of Computer Engineering at the University of California, Santa Cruz (UCSC), and is a Principal Scientist at the Palo Alto Research Center (PARC). Prior to joining UCSC in 1993, he was a Center Director at SRI International (SRI) in Menlo Park, California. He has been a Visiting Professor at Sun Laboratories and a Principal of Protocol Design at Nokia. Dr. Garcia-Luna-Aceves has published a book, more than 300 papers, and nine U.S. patents. He has directed 22 Ph.D. theses and 19 M.S. theses since he joined UCSC in 1993. He has been the General Chair of the IEEE SECON 2005 Conference; Program Co-Chair of ACM MobiHoc 2002 and ACM Mobicom 2000; Chair of the ACM SIG Multimedia; General Chair of ACM Multimedia ’93 and ACM SIGCOMM ’88; and Program Chair of IEEE MULTIMEDIA ’92, ACM SIGCOMM ’87, and ACM SIGCOMM ’86. He has served in the IEEE Internet Technology Award Committee, the IEEE Richard W. Hamming Medal Committee, and the National Research Council Panel on Digitization and Communications Science of the Army Research Laboratory Technical Assessment Board. He has been on the editorial boards of the IEEE/ACM Transactions on Networking, the Multimedia Systems Journal, and the Journal of High Speed Networks. He received the SRI International Exceptional-Achievement Award in 1985 and 1989, and is a fellow of the IEEE.     

Constrained shortest link-disjoint paths selection: a network programming based approach

Given a graph G with each link in the graph associated with two positive weights, cost and delay, we consider the problem of selecting a set of k link-disjoint paths from a node s to another node t such that the total cost of these paths is minimum and that the total delay of these paths is not greater than a specified bound. This problem, to be called the constrained shortest link-disjoint path (CSDP(k)) problem, can be formulated as an integer linear programming (ILP) problem. Relaxing the integrality constraints results in an upper bounded linear programming problem. We first show that the integer relaxations of the CSDP(k) problem and a generalized version of this problem to be called the generalized CSDP (GCSDP (k)) problem (in which each path is required to satisfy a specified bound on its delay) both have the same optimal objective value. In view of this, we focus our work on the relaxed form of the CSDP(k) problem (RELAX-CSDP(k)). We study RELAX-CSDP(k) from the primal perspective using the revised simplex method of linear programming. We discuss different issues such as formulas to identify entering and leaving variables, anti-cycling strategy, computational time complexity etc., related to an efficient implementation of our approach. We show how to extract from an optimal solution to RELAX-CSDP(k) a set of k link-disjoint s-t paths which is an approximate solution to the original CSDP(k) problem. We also derive bounds on the quality of this solution with respect to the optimum. We present simulation results that demonstrate that our algorithm is faster than currently available approaches. Our simulation results also indicate that in most cases the individual delays of the paths produced starting from RELAX-CSDP(k) do not deviate in a significant way from the individual path delay requirements of the GCSDP(k) problem.     

An efficient multiple shortest augmenting paths algorithm for constructing high performance VLSI subarray

Reconfiguring a high-performance subarray of a VLSI array with faults is to construct a maximum target array with the minimum number of long interconnects, which can reduce communication costs, capacitance and dynamic energy dissipation. An existing work proved that the high performance VLSI subarray can be constructed in polynomial time using network flow algorithm. However, because of the disadvantage of the previous network model and the low-performing of standard network flow algorithms for reconfiguration, the efficiency of these algorithms is poor for constructing the high performance VLSI subarray. In this paper, we present an efficient multiple shortest augmenting paths algorithm for rapidly constructing high performance VLSI array. Firstly, we proposed an efficient data structure to construct the network model of the VLSI array with faults, which can dramatically reduce the size of the model compared with previous algorithm. Secondly, a multiple shortest augmenting path algorithm based on the new data structure is proposed, which can significant reduce the running time. Finally, we conduct solid experiments to highlight the efficiency of the proposed method in terms of the running time compared to the standard network flow algorithms. The experimental results show that on a 64 × 64 host array with 0.1% faults, the size of the network model can be reduced by about 50% and the average improvements in running time is up to 85.10% compared with four standard network flow algorithms.     

F-TPR: fine two-phase IP routing scheme over shortest paths for hose model

This letter proposes an IP-based finely-distributed routing scheme based on two-phase routing (TPR) over shortest paths for the hose model. It is called the fine-TPR (F-TPR) scheme. Compared to the original TPR, F-TPR distributes traffic from a source node to intermediate nodes more finely, where the distribution ratio is determined for each source-destination pair. To determine an optimum set of the distribution ratios, we successfully formulate our problem as a quadratic constraint programming (QCP) formulation that can be solved by using a mathematical programming solver. Numerical results show that F-TPR greatly outperforms TPR and its performance approaches that provided by the sophisticated traffic engineering (TE) scheme of multi-protocol label switching (MPLS-TE).     

采用相邻最短遍历路径进行场景分割

提出了一种新的场景分割算法,采用相邻最短遍历路径对MPEG-2码流中的I帧进行排序,通过考察该路径中相邻I帧间的时间关系来进行场景分割。该方法在分割特殊效果连接的场景时有比较好的效果,特别适合于对视频片断中的一些反复出现的标准性场景,而这些声景前后的过滤都采用特殊效果进行分割的场合,实验也证明了这一点。     

An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands

We consider dynamic routing of holding-time aware demands under a sliding scheduled traffic model to satisfy demands' bandwidth and timing requirements. We propose an all hops optimal routing algorithm that iteratively finds all feasible paths of at most h hops at the end of h-th iteration. We prove the correctness and analyze the time complexity of the algorithm.     

Enumeration of all simple paths in a communication network

An algorithm has been developed for enumerating all simple paths in a communication network for specified terminal pairs. The efficiency of the method increases with the number of terminal pairs for which path enumeration is required. The algorithm generates the paths in ascending order of cardinality. The method is applicable to the graphs having finite non zero failure probability nodes. A FORTRAN program for implementation of the algorithm has been developed and results are reported.     

Petri net approach to enumerate all simple paths in a graph

A technique utilising the concept of reachability in a Petri net is proposed to enumerate all simple paths between two specified nodes of a graph. It is simple and requires little computation.     

An efficient pursuit automata approach for estimating stable all‐pairs shortest paths in stochastic network environments

This paper presents a new solution to the dynamic all‐pairs shortest‐path routing problem using a fast‐converging pursuit automata learning approach. The particular instance of the problem that we have investigated concerns finding the all‐pairs shortest paths in a stochastic graph, where there are continuous probabilistically based updates in edge‐weights. We present the details of the algorithm with an illustrative example. The algorithm can be used to find the all‐pairs shortest paths for the ‘statistical’ average graph, and the solution converges irrespective of whether there are new changes in edge‐weights or not. On the other hand, the existing popular algorithms will fail to exhibit such a behavior and would recalculate the affected all‐pairs shortest paths after each edge‐weight update. There are two important contributions of the proposed algorithm. The first contribution is that not all the edges in a stochastic graph are probed and, even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. The second contribution is designing a data structure, the elements of which represent the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. All the algorithms were tested in environments where edge‐weights change stochastically, and where the graph topologies undergo multiple simultaneous edge‐weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. Copyright © 2008 John Wiley & Sons, Ltd.     

Finding all the DC solutions of a certain class of piecewise-linear circuits

The problem of finding all the DC solutions of a certain class of piecewise-linear electronic circuits containing locally passive and locally active one-ports is considered in this paper. An effective method enabling us to locate the solutions is developed. The method constitutes the crucial point of an algorithm based on the idea of successive contraction, division, and elimination that is capable of determining all the solutions. Several numerical examples are given, and some comparison analyses are performed confirming the usefulness of the proposed approach.This work was supported by the State Committee for Scientific Research (KBN) under grant 8T11B0911.     

生成有向图的有向通路和有向回路的一个新算法

本文首先定义了顶点的边,度关系矩阵,由此形成通路矩阵。证明了通路矩阵生成有向通路和有向回路的条件,提出了一个系统地,无重复地生成有向的全部有向通路和向回路的新算法。     

A new simple algorithm for enumerating all minimal paths and cuts of a graph

There are many algorithms to enumerate MPS and MCS. All of these involve advanced mathematics. This paper presents a new simple algorithm to determine all minimal paths between specified single terminal pair of arbitrary graphs or to determine all minimal cuts when the graph is planar. The algorithm is based on elementary concept of graph theory and dual principle. This algorithm is fast and simple. An example illustrates the algorithm.     

Enumeration of all simple paths in a directed graph using Petri net: A systematic approach

The determination of all simple (or success) paths between two specified nodes in a directed graph finds various applications in graph theory, reliability evaluation of a system, etc. Many attempts at the problem of determining the S-T paths (simple or success paths between specified nodes S and T) have appeared in the literature [1–3]. The present paper, which utilizes the concept of the Petri net (PN), is yet another attempt at the same problem. The proposed technique is simple and tackles the problem in a systematic way. It is amenable to computer implementation.     

求有向图中源点到各结点所有路径的一种实用算法

给出了有向图中求解源结点到各顶点之间所有路径问题的一个算法,该算法能够求出他们的所有路径,并按照路径权值的大小递增排列,在算法的实现中第一次应用邻接矩阵求解各结点的前趋以便得到各结点的路径运算顺序,然后通过邻接表的数据结构实现此算法,此算法已用C语言编制的相应程序验证了其可靠性和实用性.     

A petri net approach to enumerate all system success paths for reliability evaluation of a complex system

A Petri net approach to enumerate all system success paths between a specified pair of nodes is presented. The proposed technique requires only vector additions on a single matrix. It is simple and can easily be computerized.     

Optimal mapping of virtual networks with hidden hops

Network virtualization has emerged as a solution for the Internet inability to address the required challenges caused by the lack of coordination among Internet service providers for the deployment of new services. The allocation of resources is one of the main problems in network virtualization, mainly in the mapping of virtual nodes and links to specific substrate nodes and paths, also known as the virtual network embedding problem. This paper proposes an algorithm based on optimization theory, to map the virtual links and nodes requiring a specific demand, looking for the maximization of the spare bandwidth and spare CPU in the substrate network, taking into account the CPU demanded by the hidden hops when a virtual link is mapped. The components of the virtual networks (nodes and links) that do not ask for an specific demand are then allocated following a fairness criteria.