Header menu link for other important links
X
On finding the minimum bandwidth of interval graphs
Published in
1991
Volume: 95
   
Issue: 2
Pages: 218 - 224
Abstract
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. © 1991.
About the journal
JournalInformation and Computation
ISSN08905401
Open AccessYes
Concepts (4)
  •  related image
    Computer programming - algorithms
  •  related image
    INTERVAL GRAPHS
  •  related image
    MINIMUM BANDWIDTH
  •  related image
    Mathematical techniques