Testing Bandwidth k for k -Connected Graphs
Konrad Engel, Sven Guttmann · SIAM Journal on Discrete Mathematics · 2003
We present a linear-time algorithm to decide whether a given k-connected graph has bandwidth k, where k is a fixed positive integer. This improves the general O(n k )-time-algorithm of Gurari and Sudborough, based on a dynamic programming approach of Saxe, for the recognition of bandwidth-k graphs on n vertices in the special case of connectivity k.