Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-017 | 5th May 1997 00:00

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

RSS-Feed

Abstract:

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 of this problem are known to be efficiently approximable. In
this paper we present the first constant approximation ratio
algorithms on dense instances of this problem.



ISSN 1433-8092 | Imprint