skip to main content
research-article

Even Faster Exact Bandwidth

Published: 01 January 2012 Publication History

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*(10n)-time and polynomial space algorithm.
In this article we present a new algorithm that solves Bandwidth in O*(5n) time and O*(2n) space. Then, we take a closer look and introduce a major modification that makes it run in O(4.83n) time with a cost of a O*(4n) 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.

References

[1]
Assman, S., Peck, G., Syslo, M., and Zak, J. 1981. The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Algeb. Disc. Meth. 2, 387--393.
[2]
Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. 1994. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy (extended abstract). In Proceedings of the ACM Symposium on Theory of Computing, 449--458.
[3]
Cygan, M. and Pilipczuk, M. 2008. Faster exact bandwidth. In Proceedings of the International Workshop on Graph-Theoretic Concept in Computer Science (WG’08). 101--109.
[4]
Feige, U. 2000. Coping with the NP-hardness of the graph bandwidth problem. In Proceedings of the Scandanavian Workshop on Algorithm Theory (SWAT’00). 10--19.
[5]
Fomin, F. V., Grandoni, F., and Kratsch, D. 2005. Measure and conquer: Domination-a case study. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’05). 191--203.
[6]
Fomin, F. V., Grandoni, F., and Kratsch, D. 2009. A measure & conquer approach for the analysis of exact algorithms. J. ACM 56, 5.
[7]
Garey, M., Graham, R., Johnson, D., and Knuth, D. 1978. Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34, 477--495.
[8]
Kleitman, D. and Vohra, R. 1990. Computing the bandwidth of interval graphs. SIAM J. Disc. Math. 3, 373--375.
[9]
Lee, J. R. 2009. Volume distortion for subsets of Euclidean spaces. Disc. Computat. Geom. 41, 4, 590--615.
[10]
Monien, B. 1986. The bandwidth-minimization problem for caterpillars with hairlength 3 is NP-complete. SIAM J. Algeb. Disc. Meth. 7, 505--512.
[11]
Unger, W. 1998. The complexity of the approximation of the bandwidth problem. In Proceedings of the Symposium on Foundations of Computer Science (FOCS’98). 82--91.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 8, Issue 1
January 2012
191 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/2071379
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2012
Accepted: 01 November 2009
Revised: 01 November 2009
Received: 01 November 2008
Published in TALG Volume 8, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Bandwidth
  2. Measure & Conquer
  3. exact algorithms

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • Polish Ministry of Science and Higher Education

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)21
  • Downloads (Last 6 weeks)2
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media