NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
复制标题
平面图中放射着色的 NP 完备性结果和有效近似
DOI：
10.1007/3-540-44612-5_32
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
Dimitris Fotakis;S. Nikoletseas;V. P. Lesta;P. Spirakis
无线电网络中的频率分配问题（FAP）是利用频率复用将频率分配给发射机同时将信号干扰保持在可接受水平的问题。FAP通常由图着色问题的变化来建模。图G（V，E）的放射染色（RC）是指一个分配函数Φ：V →IN，当u，v是G中的邻图时，满足φ（u）-Φ（v）≥ 2，当u，vinG的最小距离为2时，满足φ（u）-Φ（v）≥1.所使用的离散数和频率范围分别称为阶数和跨度。辐射着色问题的优化问题是最小化问题的阶数或最小化问题。本文证明了平面图的最小跨度RCP是NP-完全的，并给出了一个O（nΔ）时间算法（τ V β =n），该算法可得到平面图G的一个辐射染色，该辐射染色在一个趋于2的比率内逼近最小阶数（其中Δ是G的最大度）.最后，我们给出了当λ ≥ 4λ + 50时，平面图G的λ色有效辐射着色的完全多项式随机逼近方案（fpras）。
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. The Radiocoloring (RC) of a graph G(V,E) is an assignment functionΦ:V →IN such that ¦Φ(u)-Φ(v)≥ 2, whenu;vare neighbors inG, and ¦Φ(u)-Φ(v)≥1 when the minimum distance ofu;vinGis two. The discrete number and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove thatthe min span RCP is NP-complete for planar graphs.Next, we provide an O(nΔ) time algorithm (¦V¦ =n) which obtains a radiocoloring of a planar graphGthatapproximates the minimum order within a ratio which tends to 2(where Δ the maximum degree ofG). Finally, we provide afully polynomial randomized approximation scheme(fpras) for thenumber of valid radiocolorings of a planar graph Gwith λ colors, in the case λ ≥ 4λ + 50.