Shi-Sheng Li

Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges...