A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs - David H. Muradian (Изд-во НАН РА)
In this paper we show that the Bandwidth Minimization problem for interval graphs can be solved in time O(n∆2log(∆)), where n is the vertex number and Δ is the maximal degree of vertex of the interval graph.
Keywords: Mathematics; Science; Graph theory; Algorithm