Even Faster Exact Bandwidth
Open Access
- 1 January 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 8 (1) , 1-14
Abstract
We deal with exact algorithms for Bandwidth , a long studied NP-hard problem. For a long time nothing better than the trivial O * ( n !) 1 exhaustive search was known. In 2000, Feige and Kilian [Feige 2000] came up with a O * (10 n )-time and polynomial space algorithm. In this article we present a new algorithm that solves Bandwidth in O * (5 n ) time and O * (2 n ) space. Then, we take a closer look and introduce a major modification that makes it run in O (4.83 n ) time with a cost of a O * (4 n ) space complexity. This modification allowed us to perform the Measure & Conquer analysis for the time complexity which was not used for graph layout problems before.Keywords
All Related Versions
Funding Information
- Polish Ministry of Science and Higher Education (N206 005 32/0807)
This publication has 8 references indexed in Scilit:
- A measure & conquer approach for the analysis of exact algorithmsJournal of the ACM, 2009
- Volume Distortion for Subsets of Euclidean SpacesDiscrete & Computational Geometry, 2009
- Measure and Conquer: Domination – A Case Study2005
- Beyond NP -completeness for problems of bounded width (extended abstract): hardness for the W hierarchy1994
- Computing the Bandwidth of Interval GraphsSIAM Journal on Discrete Mathematics, 1990
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1986
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2SIAM Journal on Algebraic Discrete Methods, 1981
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978