Approximating Bandwidth by Mixing Layouts of Interval Graphs

• Author(s) / Creator(s)

  • Kratsch, D.
  • Stewart, Lorna

• 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

  1998

• Subjects / Keywords

  • Algorithms
  • Approximation
  • Bandwidth
  • Circular-arc graphs
  • Algorithmics
  • Interval graphs
  • Chordal graphs
  • Polygon graphs

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3VQ2SB4J

• License

  Attribution 3.0 International