article · SIAM Journal on Discrete Mathematics · 1990

Computing the Bandwidth of Interval Graphs

Cited by 66Abstract and details only

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

Cite this paper

APA 7

Kleitman, D. J., & Vohra, R. (1990). Computing the Bandwidth of Interval Graphs. SIAM Journal on Discrete Mathematics, 3(3), 373–375. https://doi.org/10.1137/0403033

MLA 9

Kleitman, Daniel J., and Rakesh Vohra. “Computing the Bandwidth of Interval Graphs.” SIAM Journal on Discrete Mathematics, vol. 3, no. 3, 1990, pp. 373–75, https://doi.org/10.1137/0403033.

Chicago

Kleitman, Daniel J., and Rakesh Vohra. 1990. “Computing the Bandwidth of Interval Graphs.” SIAM Journal on Discrete Mathematics 3 (3): 373–75. https://doi.org/10.1137/0403033.

Harvard

Kleitman, D.J. and Vohra, R. (1990) ‘Computing the Bandwidth of Interval Graphs’, SIAM Journal on Discrete Mathematics, 3(3), pp. 373–375. Available at: https://doi.org/10.1137/0403033.

BibTeX

@article{kleitman1990computing,
  title = {{Computing the Bandwidth of Interval Graphs}},
  author = {Kleitman, Daniel J. and Vohra, Rakesh},
  journal = {SIAM Journal on Discrete Mathematics},
  volume = {3},
  number = {3},
  pages = {373--375},
  year = {1990},
  doi = {10.1137/0403033}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.