Affordable Access

Publisher Website

Bandwidth and distortion revisited

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Volume
160
Identifiers
DOI: 10.1016/j.dam.2011.10.032
Keywords
  • Bandwidth
  • Distortion
  • Exact Algorithms
  • Exponential Algorithms
Disciplines
  • Computer Science

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.