The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
スポンサーリンク
概要
- 論文の詳細を見る
Given an edge-weighted undirected graph and two vertices s and t, the next-to-shortest path problem is to find an st-path whose length is minimum among all st-paths of lengths strictly larger than the shortest path length. The problem is shown to be polynomially solvable if all edge weights are positive, while the complexity status for the nonnegative weight case was open. In this paper we show that the problem in undirected graphs admits a polynomial-time algorithm even if all edge weights are nonnegative, solving the open problem. To solve the problem, we introduce a common generalization of the undirected graph version and the acyclic digraph version of the k vertex-disjoint paths problem.
- 2011-11-11
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nagamochi
Graduate School Of Informatics Kyoto University
-
Nagamochi Hiroshi
Graduate School Of Informatics Kyoto University
-
Hiroshi Nagamochi
Department Of Applied Mathematics And Physics Kyoto University
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Cong Zhang
Graduate School Of Informatics Kyoto University
関連論文
- Constant Time Generation of Trees with Degree Bounds
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- Survivable Network Design Problems with Weighted Degree Constraints (Combinatorial Optimization and Discrete Algorithms)
- Contention-Free λ-Planes in Optically Burst-Switched WDM Networks(Internet)
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- Protein complex prediction via improved verification methods using constrained domain-domain matching
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Indexing All Rooted Subgraphs of a Rooted Graph
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS