This is a decommissioned version of ERA which is running to enable completion of migration processes. All new collections and items and all edits to existing items should go to our new ERA instance at https://ualberta.scholaris.ca - Please contact us at erahelp@ualberta.ca for assistance!
- 178 views
- 213 downloads
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
- 1998
-
- Subjects / Keywords
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International