Approximating Bandwidth by Mixing Layouts of Interval Graphs

  • Author(s) / Creator(s)
  • Technical report TR98-06. In this paper, we examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). All of these graph classes admit efficient approximation algorithms which are based on exact or approximate bandwidth layouts of related interval graphs. Specifically, we obtain a bandwidth approximation algorithm for circular-arc graphs that has performance ratio 2 and executes in O(n log^2 n) time, or performance ratio 4 while taking O(n) time. For chordal graphs with not more than k leaves in the clique tree, we obtain a performance ratio of 2k in O(n) time, and our algorithm for k-polygon graphs has performance ratio 2k^2 and runs in time O(n^3). | TRID-ID TR98-06

  • Date created
  • Subjects / Keywords
  • Type of Item
  • DOI
  • License
    Attribution 3.0 International