Bandwidth and Distortion Revisited

Details Bandwidth and Distortion Revisited Bandwidth and Distortion Revisited

2010-04-28

arxiv.org/abs/1004.5012v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.363^n) time and polynomial space. For BANDWIDTH, this improves O^*(10^n) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c^n) time we are aware of. As a byproduct, we enhance the O(5^{n+o(n)})-time and O^*(2^n)-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383^n) time and space.

Affiliated with

Also associated with

No associations

Rating

Bandwidth and Distortion Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bandwidth and Distortion Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bandwidth and Distortion Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-68819