Approximating bandwidth by mixing layouts of interval graphs

作     者：Kratsch, D Stewart, L 

作者机构：Univ Jena Fak Math & Informat D-07740 Jena Germany Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：2002年第15卷第4期

页      面：435-449页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Natural Sciences and Engineering Research Council of Canada 

主　　题：interval graphs circular-arc graphs chordal graphs polygon graphs bandwidth problem approximation algorithm 

摘      要：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). We show that 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 executes in O(n log(2) n) time and has performance ratio 2, which is the best possible performance ratio of any polynomial time bandwidth approximation algorithm for circular-arc graphs. For chordal graphs with at most k leaves in the clique tree, we obtain a performance ratio of 2k in O(k(n+m)) time, and our algorithm for k-polygon graphs has performance ratio 2k(2) and runs in time O(n(3)).