A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs

L. H. Harper, “Optimal numberings and isoperimetric problems on graphs”, Journal of Combinatorial Theory, vol.1, no. 3, pp. 385–393, 1966.

C. Papadimitriou, “The NP-completeness of the bandwidth minimization problem”, Computing, vol. 16, pp. 263-270, 1976.

D. Muradian, “The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete”, Theoretical Computer Science, “Selected Papers in Honour of Lawrence Harper”, vol. 307, no. 3, pp. 567-572, 2003.

Y.-L. Lai, Bandwidth, edgesum and profile of graphs. Ph.D. thesis, Dept. of Computer Science, Western Michigan Univ, 1997.

T. Kloks, D. Kratsch and H. Muller, “Bandwidth of chain graphs”, Information Processing Letters, vol. 68, no. 6, pp. 313-315, 1998.

S. F. Assman, Peck et al., “The bandwidth of caterpillars with hair of length 1 and 2”, SIAM Journal on Algebraic and Discrete Methods, vol. 2, pp. 387-393, 1981.

Д. О. Мурадян, “Полиномиальный алгоритм для нахождения минимаксных нумераций графов интервалов”, Академия Наук Арм. ССР, в. 82, pp. 64-66, 1986.

D. Kleitman and R. Vohra, “Computing the bandwidth of interval graphs”, SIAM J. Discrete Math., vol. 3, no. 3, pp. 373-375, 1990.

R. Mahesh, C. P. Rangan and A. Srinivasan, “On finding the minimum bandwidth of interval graphs”, Information and Computation, vol. 95, no. 2, pp. 218-224, 1991.

A. P Sprague, “An O(n log n) algoritm for bandwidth of interval graphs”, SIAM Journal on Discrete Mathematics, vol. 7, no. 2, pp. 213-220, 1994.