Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(<Special Section>Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
スポンサーリンク
概要
- 論文の詳細を見る
An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.
- 社団法人電子情報通信学会の論文
- 2007-04-01
著者
-
TAOKA Satoshi
Graduate School of Engineering, Hiroshima University
-
WATANABE Toshimasa
Graduate School of Engineering, Hiroshima University
-
Taoka Satoshi
Graduate School Of Engineering Hiroshima University
-
Taoka Satoshi
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
Watanabe Toshimasa
Graduate School Of Engineering Hiroshima University
-
TAKAFUJI Daisuke
Graduate School of Engineering, Hiroshima University
-
IGUCHI Takashi
Graduate School of Engineering, Hiroshima University
-
Watanabe Toshimasa
Hiroshima Univ. Higashi‐hiroshima Jpn
-
Iguchi Takashi
Graduate School Of Engineering Hiroshima University
-
Takafuji Daisuke
Graduate School Of Engineering Hiroshima University
-
Watanabe Toshimasa
Graduate School Of Engineering Hiroshima Univ.
関連論文
- Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
- A Fast Algorithm for (σ+1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints
- A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
- A (2 - 2/|L|)-Approximation Algorithm R2VS or R2ES to 2-Vertex- or 2-Edge-Connect Specified Vertices in a Graph
- Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
- Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
- Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
- Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)
- Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
- Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
- Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Performance comparison of algorithms for the dynamic shortest path problem (グラフアルゴリスム)
- Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
- A linear time algorithm for tri-connectivity augmentation of bi-connected graphs with upper bounds on vertex-degree increase (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
- On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, Foundations of Computer Science)
- A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
- A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- Tri-connectivity augmentation problems for bi-connected graphs with upper bounds on vertex-degree increase (ネツトワークの信頼性)
- FOREWORD
- The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
- A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
- Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs
- Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets