Path Problems in Skew-Symmetric Graphs

摘要

The authors study path problems in skew-symmetric graphs. These problemsgeneralize the standard graph reachability and shortest paths problems. They develop duality theory for the skew-symmetric problems and use it to design efficient algorithms for the problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.