SIAM Journal on Discrete Mathematics · 1990 · 67 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationAlgorithm AnalysisComputational ComplexityGraph AlgorithmsGraph TheoryComplexityComputational Complexity Of Graph Algorithms
In this note, an $O ( | V |k )$ algorithm is described for determining whether an interval graph on $| V |$ vertices has a bandwidth less than or equal to a given integer k. While the algorithm is not the first to resolve this problem, it does admit a shorter proof of its correctness than a previous algorithm of the same complexity due to Kratsch (Information and Computation, 74 (1987), pp. 140–158).
7
The NP-Completeness of the bandwidth minimization problem
Ch. H. Papadimitriou · Computing · 1976 · 409 citations
The NP-completeness column: an ongoing guide
David Johnson · Journal of Algorithms · 1985 · 239 citations