On finding the minimum bandwidth of interval graphs

TitleOn finding the minimum bandwidth of interval graphs
Publication TypeJournal Articles
Year of Publication1991
AuthorsMahesh R, Rangan C.P, Srinivasan A
JournalInformation and Computation
Pagination218 - 224
Date Published1991/12//
ISBN Number0890-5401

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.