A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs


  • David H. Muradian Institute for Informatics and Automation Problems of NAS RA


Graph layout, Bandwidth, 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.




How to Cite

Muradian, D. H. (2021). A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs. Mathematical Problems of Computer Science, 46, 73–80. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/151