Channel assignment on graphs of bounded treewidth

被引：13
作者：
McDiarmid, C
Reed, B
机构：
[1] Univ Oxford, Dept Stat, Oxford OX1 3TG, England
[2] Univ Paris 06, CNRS, Paris, France
[3] McGill Univ, Dept Comp Sci, Montreal, PQ, Canada
来源：
DISCRETE MATHEMATICS | 2003年 / 273卷 / 1-3期
关键词：
channel assignment; bounded treewidth; graph colouring;
D O I：
10.1016/S0012-365X(03)00236-X
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The following 'constraint matrix span problem' arises in the assignment of radio channels in cellular communications systems. Given a graph G with a positive integer length l(xy) for each edge xy, and given a positive integer B, can we assign to each vertex x a channel phi(x) from 1,...,B such that \phi(x) - phi(y)\ greater than or equal to l(xy) for each edge xy? We show that this problem is NP-complete for graphs of treewidth at most 3, but there is a fully polynomial time approximation scheme for the problem on graphs of bounded treewidth. We see also that it is NP-complete for graphs which can be made bipartite by deleting a single vertex. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：183 / 192
页数：10
相关论文
共 50 条
[21]   Scheduling a Pipelined Operator Graph of Bounded Treewidth [J].
Li, Shuguang ;
Xin, Xiao .
MATERIALS, MECHATRONICS AND AUTOMATION, PTS 1-3, 2011, 467-469 :1102-+
[22]   Improved Steiner tree algorithms for bounded treewidth [J].
Chimani, Markus ;
Mutzel, Petra ;
Zey, Bernd .
JOURNAL OF DISCRETE ALGORITHMS, 2012, 16 :67-78
[23]   A channel assignment problem for optical networks modelled by Cayley graphs [J].
Zhou, SM .
THEORETICAL COMPUTER SCIENCE, 2004, 310 (1-3) :501-511
[24]   Steepest ascent can be exponential in bounded treewidth problems [J].
Cohen, David A. ;
Cooper, Martin C. ;
Kaznatcheev, Artem ;
Wallace, Mark .
OPERATIONS RESEARCH LETTERS, 2020, 48 (03) :217-224
[25]   Tractable database design and datalog abduction through bounded treewidth [J].
Gottlob, Georg ;
Pichler, Reinhard ;
Wei, Fang .
INFORMATION SYSTEMS, 2010, 35 (03) :278-298
[26]   Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth [J].
Czumaj, A ;
Halldórsson, MM ;
Lingas, A ;
Nilsson, J .
INFORMATION PROCESSING LETTERS, 2005, 94 (02) :49-53
[27]   On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth [J].
Igor Razgon .
Algorithmica, 2016, 75 :277-294
[28]   On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth [J].
Razgon, Igor .
ALGORITHMICA, 2016, 75 (02) :277-294
[29]   A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth [J].
Shoudai, Takayoshi ;
Yamada, Takashi .
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2017, E100A (09) :1764-1772
[30]   A bound on the treewidth of planar even-hole-free graphs [J].
Silva, Ana ;
da Silva, Aline Alves ;
Sales, Claudia Linhares .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (12) :1229-1239
12345