Abstract.
We review several approaches of coping with NP-hardness, and see how they apply (if at all) to the problem of computing the bandwidth of a graph.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
L. Adleman. “Algorithmic Number Theory-The Complexity Contribution”. Proc. of 35th FOCS, 1994, 88–113.
S. Assman, G. Peck, M. Syslo, J Zak. “The bandwidth of caterpillars with hairs of length 1 and 2”. SIAM J. Algebraic Discrete Methods 2 (1981), 387–393.
G. Blache, M. Karpinski, J. Wirtgen. “On approximation intractability of the bandwidth problem”. Manuscript, 1998.
A. Blum, G. Konjevod, R. Ravi, S. Vempala. “Semidefinite relaxations for minimum bandwidth and other vertex-ordering problems”. Proc. of 30th STOC, 1998, 100–105.
A. Blum, J. Spencer. “Coloring Random and Semi-Random k-Colorable Graphs”. Journal of Algorithms 19, 204–234, 1995.
H. Bodlaender, M. Fellows, M. Hallet. “Beyond NP-completeness for problems of bounded width: hardness for the W Hierarchy”. Proc. of 26th STOC, 1994, 449–458.
P. Chinn, J. Chvatalova, A. Dewdney, N. Gibbs. “The bandwidth problem for graphs and matrices-a survey”. Journal of Graph Theory, 6 (1982), 223–254.
F. Chung, P. Seymour. “Graphs with small bandwidth and cutwidth”. Discrete Mathematics75 (1989) 113–119.
J. Chvatalova. On the bandwidth problem for graphs, Ph.D. dissertation, University of Waterloo, 1980.
E. Cuthill, J. McKee. “Reducing the bandwidth of sparse symmetric matrices”. A CM National Conference Proceedings, 24, 1969, 157–172.
R. Downey, M. Fellows. Parameterized Complexity. Sringer-Verlag New York, 1999.
U. Feige. “Approximating the Bandwidth via Volume Respecting Embeddings”. Journal of Computer and System Sciences, to appear. (A preliminary version appeared in the proceedings of the 30th STOC, 1998, 90–99.)
U. Feige, J. Kilian. “On limited versus polynomial nondeterminism”. Chicago Journal of Theoretical Computer Science, 12 March 1997. http://www.cs.uchicago.edu/pub/publications/cjtcs/index.html
U. Feige, J. Kilian. “Heuristics for semirandom graph problems” Journal of Computer and System Sciences, to appear. (Preliminary version in Proc. of 39th FOCS, 1998, 674–683)
U. Feige, J. Kilian. “Exponential time algorithms for computing the bandwidth of a graph”. Manuscript in preparation.
U. Feige, R. Krauthgamer. “Improved performance guarantees for bandwidth minimization heuristics”. Manuscript, 1998.
M. Garey, R. Graham, D. Johnson, D. Knuth. “Complexity results for bandwidth minimization”. SIAM J. Appl. Math. 34 (1978), 477–495.
O. Goldreich. “Notes on Levin’s Theory of Average-Case Complexity”. Manuscript, 1997. http://www.wisdom.weizmann.ac.il/home/odedg
A. Gupta. “Improved bandwidth approximation algorithms for trees”. Proc. SODA 2000.
E. Gurari, I. Sudborough. “Improved dynamic programming algorithms for bandwidth minimization and the min-cut linear arrangement problems”. J. Algorithms, 5 (1984), 531–546.
J. Haralambides, F. Makedon, B. Monien. “Bandwidth minimization: an approximation algorithm for caterpillars”. Math Systems Theory 24, 169–177 (1991).
R. Impagliazzo, R. Paturi. “Complexity of k-S AT”. Proc. Computational Complexity, 1999.
R. Impagliazzo, R. Paturi, F. Zane. “Which problems have strongly exponential complexity”. Proc. FOCS 1988, 653–663.
M. Karpinski, J. Wirtgen, A. Zelikovsky. “An approximation algorithm for the bandwidth problem on dense graphs”. ECCC TR97-017.
D. Kleitman, R. Vohra. “Computing the bandwidth of interval graphs”. SIAM J. Discrete Math., 3 (1990), 373–375.
T. Kloks, D. Kratsch, H. Muller. “Approximating the bandwidth for asteroidal triple-free graphs”. In Algorithms-ESA’ 95, Paul Spirakis (Ed.), Lecture Notes in Computer Science 979, 434–447, Springer.
L. Levin. “Average case complete problems”. SIAM J. Comput, 15(1):285–286, 1986.
B. Monien. “The bandwidth-minimization problem for caterpillars with hair-length 3 is NP-complete”. SIAM J. Algebraic Discrete Methods 7 (1986), 505–512.
C. Papadimitriou. “The NP-completeness of the bandwidth minimization problem”. Computing 16 (1976), 263–270.
J. Saxe. “Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time”. SIAM Journal on Algebraic Methods 1 (1980), 363–369.
J. Turner. “On the probable performance of heuristics for bandwidth minimization”. SIAM J. Comput., 15, (1986), 561–580.
W. Unger. “The complexity of the approximation of the bandwidth problem”. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, 82–91.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feige, U. (2000). Coping with the NP-Hardness of the Graph Bandwidth Problem. In: Algorithm Theory - SWAT 2000. SWAT 2000. Lecture Notes in Computer Science, vol 1851. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44985-X_2
Download citation
DOI: https://doi.org/10.1007/3-540-44985-X_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67690-4
Online ISBN: 978-3-540-44985-0
eBook Packages: Springer Book Archive