Bandwidth and distortion revisited

In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the Bandwidth problem) and for finding an embedding of a given graph into a line that minimizes distortion (the Distortion problem). For both problems we develop algorithms that work in O(9.363n) time and polynomial space. For Bandwidth, this improves O∗(10n) algorithm by Feige and Kilian from 2000, for Distortion this is the first polynomial space exact algorithm that works in O(cn) time we are aware of. As a byproduct, we enhance the O(5n+o(n))-time and O∗(2n)-space algorithm for Distortion by Fomin et al. to an algorithm working in O(4.383n)-time and space.