Home  About us  Contact
 

Path Algorithm (path + algorithm)

Distribution by Scientific Domains
Engineering71%

Kinds of Path Algorithm

  • shortest path algorithm
    		•

    Selected Abstracts

    GPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networks

    INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 10 2004
    Sudip Misra
    Abstract This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link-costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to-date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ,statistical' average network, which converges irrespective of whether there are new changes in link-costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link-cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd. [source]

    Tightest constraint first: An efficient delay sensitive multicast routing algorithm

    INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 7 2005
    Gang FengArticle first published online: 1 APR 200
    Abstract As a key issue in multicast routing with quality of service (QoS) support, constrained minimum Steiner tree (CMST) problem has been a research focus for more than a decade, and tens of heuristics have been developed to solve this NP-complete problem. Among all the previously proposed algorithms, the bounded shortest path algorithm (BSMA) (IEEE INFOCOM'95 1995; 1:377,385) have been proved to be capable of producing a multicast tree that has on average the lowest cost. However, such an excellent cost performance is accompanied with an extremely high time complexity. Recently, Feng et al. presented an alternative implementation of BSMA, which makes use of the latest research results on the delay-constrained least cost (DCLC) routing problem. Simulations indicate that, in comparison with the original implementation, the alternative implementation has a much lower time complexity with virtually identical cost performance, and it also runs much faster than many renowned heuristics such as KPP (IEEE/ACM Trans. Networking 1993; 1(3):286,292) and CAO (The design and evaluation of routing algorithms for real-time channels. Technical Report ICSI TR-94-024, International Computer Science Institute, University of California at Berkeley, June 1994). In this paper, we propose a brand new heuristic TCF, which is based on an idea called ,tightest constraint first.' TCF runs a DCLC heuristic only once for each destination and therefore has a provably low time complexity. We further propose an iterative heuristic ITCF, which uses TCF to obtain an initial tree and then gradually refines it. Extensive simulations demonstrate that, in the average sense, TCF can achieve a cost performance comparable to or better than that of BSMA, the cost performance of ITCF is even better than that of TCF, TCF runs approximately twice as fast as ITCF, and ITCF runs 2,4 times as fast as the best implementation of BSMA. Copyright © 2005 John Wiley & Sons, Ltd. [source]

    A novel QoS routing protocol for LEO and MEO satellite networks

    INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS AND NETWORKING, Issue 6 2007
    Yunhui Zhou
    Abstract The rapid advance of communication and satellite technology pushes broadband satellite networks to carry on multimedia traffic. However, the function of onboard routing cannot be provided in existing satellite networks with inter-satellite links, and quality of service (QoS) of satellite networks cannot be reliably guaranteed because of great difficulties in processing of long distance-dependent traffic. In this paper, a two-layered low-Earth orbit and medium-Earth orbit satellite network (LMSN) is presented. A novel hierarchical and distributed QoS routing protocol (HDRP) is investigated, and an adaptive bandwidth-constrained minimum-delay path algorithm is developed to calculate routing tables efficiently using the QoS metric information composed of delays and bandwidth. The performance of LMSN and HDRP is also evaluated through simulations and theoretical analysis. Copyright © 2007 John Wiley & Sons, Ltd. [source]

    Performance evaluation of adaptive routing algorithms in packet-switched intersatellite link networks

    INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS AND NETWORKING, Issue 2 2002
    Mihael Mohor
    Abstract This paper addresses the performance evaluation of adaptive routing algorithms in non-geostationary packet-switched satellite communication systems. The dynamic topology of satellite networks and variable traffic load in satellite coverage areas, due to the motion of satellites in their orbit planes, pose stringent requirements to routing algorithms. We have limited the scope of our interest to routing in the intersatellite link (ISL) segment. In order to analyse the applicability of different routing algorithms used in terrestrial networks, and to evaluate the performance of new algorithms designed for satellite networks, we have built a simulation model of a satellite communication system with intersatellite links. In the paper, we present simulation results considering a network-uniform source/destination distribution model and a uniform source,destination traffic flow, thus showing the inherent routing characteristics of a selected Celestri-like LEO satellite constellation. The updates of the routing tables are centrally calculated according to the Dijkstra shortest path algorithm. Copyright © 2002 John Wiley & Sons, Ltd. [source]

    An improved direct labeling method for the max,flow min,cut computation in large hypergraphs and applications

    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2003
    Joachim Pistorius
    Algorithms described so far to solve the maximum flow problem on hypergraphs first necessitate the transformation of these hypergraphs into directed graphs. The resulting maximum flow problem is then solved by standard algorithms. This paper describes a new method that solves the maximum flow problem directly on hypergraphs, leading to both reduced run time and lower memory requirements. We compare our approach with a state,of,the,art algorithm that uses a transformation of the hypergraph into a directed graph and an augmenting path algorithm to compute the maximum flow on this directed graph: the run,time complexity as well as the memory space complexity are reduced by a constant factor. Experimental results on large hypergraphs from VLSI applications show that the run time is reduced, on average, by a factor approximately 2, while memory occupation is reduced, on average, by a factor of 10. This improvement is particularly interesting for very large instances, to be solved in practical applications. [source]

    A dynamic shortest path algorithm using multi-step ahead link travel time prediction

    JOURNAL OF ADVANCED TRANSPORTATION, Issue 1 2005
    Young-Ihn Lee
    Abstract In this paper, a multi-step ahead prediction algorithm of link travel speeds has been developed using a Kalman filtering technique in order to calculate a dynamic shortest path. The one-step and the multi-step ahead link travel time prediction models for the calculation of the dynamic shortest path have been applied to the directed test network that is composed of 16 nodes: 3 entrance nodes, 2 exit nodes and 11 internal nodes. Time-varying traffic conditions such as flows and travel time data for the test network have been generated using the CORSIM model. The results show that the multi-step ahead algorithm is compared more favorably for searching the dynamic shortest time path than the other algorithm. [source]

    A dynamic programming algorithm for the conditional covering problem on tree graphs

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2005
    Jennifer A. Horne
    Abstract In a previous article, we presented algorithms for solving the Conditional Covering Problem (CCP) on path and extended star graphs. The CCP on these graphs can be solved in O(n2) time, where n is the number of nodes in the graph. In this article, we propose a new dynamic programming procedure to solve the CCP on tree graphs. This recursion works from the leaf nodes of the tree up to the root node, using notions of protected and unprotected costs as done for the CCP path algorithm in our previous work. We introduce new preliminary routines and data structures to merge information from subpaths and subtrees, resulting in an O(n4) algorithm to optimally solve the problem. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 186,197 2005 [source]