CAJ | 학술논문

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d.这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图.就输入图的边是否带权,分别设计了多项式时间近似算法.当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图.算法输出的度数有界支撑子图可以用作无线网状网络的传输子网.
연구료원우무선망상망락적도수유계최대지탱자도문제:급정련통도G=(V,E)화정정수d≥2,구G적일개최대지탱자도H,만족대V중매개정점v,v재H중적도수dH(v)불초과d.저리,지탱자도지도G적일개련통이차포괄G중소유정점적자도.취수입도적변시부대권,분별설계료다항식시간근사산법.당수입도위무권도시,증명료근사산법적근사비위2;당수입도위부권도시,증명료산법수출일개최대도수불초과d+1、권중불저우최우해권중1/(d+2)적지탱자도.산법수출적도수유계지탱자도가이용작무선망상망락적전수자망.
The bounded degree maximum spanning sub-graph problem arising from wireless mesh networks was studied. Given a connected graph G-(V, E)and a positive integer d≥2, the problem aims to find a maximum spanning sub-graph H of G with the constraint: for each vertex v∈V, the degree of v in H, d_H(v)≤d. Here, a spanning subgraph of G is a connected sub-graph in G which contains all the vertices of G. Polynomial time approximation algorithms were proposed for edge un-weighted case and edge weighted case respectively. When input graphs are edge un-weighted, a 2-approximation algorithm is designed. When input graphs are edge weighted, the designed algorithm always outputs a spanning sub-graph whose maximum degree is no more than d+1 arid weight is at least OPT (G)/d+2, where OPT (G)is the weight of optimal solutions. The bounded degree spanning sub-graph output by the algorithm can be used as a transport sub-network in wireless mesh networks.