ERA

Download the full-sized PDF of Approximating Bandwidth by Mixing Layouts of Interval GraphsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3VQ2SB4J

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Approximating Bandwidth by Mixing Layouts of Interval Graphs Open Access

Descriptions

Author or creator
Kratsch, D.
Stewart, Lorna
Additional contributors
Subject/Keyword
Algorithmics
bandwidth
algorithms
chordal graphs
polygon graphs
interval graphs
circular-arc graphs
approximation
Type of item
Report
Language
English
Place
Time
Description
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).
Date created
1998
DOI
doi:10.7939/R3VQ2SB4J
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-30T22:14:52.583+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 485354
Last modified: 2015:10:12 20:24:06-06:00
Filename: TR98-06.pdf
Original checksum: b91896850eb61c0899cf957f2dbd54dd
Well formed: true
Valid: true
Page count: 20
Activity of users you follow
User Activity Date