Log-space Algorithms for Paths and Matchings in k-trees

Bireswar Das, Samir Datta, Prajakta Nimbhorkar

Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [JT07]. However, for graphs of tree-width larger th…