TY - JOUR T1 - On finding the minimum bandwidth of interval graphs JF - Information and Computation Y1 - 1991 A1 - Mahesh,R. A1 - Rangan,C.Pandu A1 - Srinivasan, Aravind AB - Let G = (V, E) be an interval graph, with |V| = n, and |E| = m. An O(n2 log n) algorithm was proposed in Kratsch (Inform Comput. 74, 140–158 (1987)) to find the bandwidth of G. We show that this algorithm is wrong, and provide a corrected version of the same. Also, it was observed in [4] that the bandwidth of a proper interval graph can be computed in O(n log n + m) time. We show how this idea can be modified slightly to yield an O(n = m) algorithm. VL - 95 SN - 0890-5401 UR - http://www.sciencedirect.com/science/article/pii/0890540191900454 CP - 2 M3 - 10.1016/0890-5401(91)90045-4 ER -