Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BANDWIDTH PROBLEM:
Reports tagged with Bandwidth Problem:
TR97-017 | 5th May 1997
Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

The bandwidth problem is the problem of numbering the vertices of a
given graph $G$ such that the maximum difference between the numbers
of adjacent vertices is minimal. The problem has a long history and
is known to be NP-complete Papadimitriou [Pa76]. Only few special
cases ... more >>>




ISSN 1433-8092 | Imprint