Computing the Bandwidth of Interval Graphs

Daniel J. Kleitman, Rakesh Vohra

SIAM Journal on Discrete Mathematics · 1990 · 67 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

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).

References

7