A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

被引：0
作者：
Tzeng, Chi-Hung [2 ]
Jiang, Jehn-Ruey [1 ]
Huang, Shing-Tsaan [1 ]
机构：
[1] Natl Cent Univ, Dept Comp Sci & Informat Engn, Jhongli, Taiwan
[2] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu 30043, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 10期
关键词：
Bipartite graph; Fault tolerance; Planar graph; Self-stabilization; Spanning tree; PLANAR SUBGRAPH; SYSTEMS; GRAPHS;
D O I：
10.1016/j.ipl.2009.01.013
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The maximum planarization problem is to find a spanning planar subgraph having the largest number of edges for a given graph. In this paper, we propose a self-stabilizing algorithm to solve this problem for complete bipartite networks. The proposed algorithm finds the maximum planar subgraph of 2n-4 edges in O(n) rounds, where n is the number of nodes. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：518 / 522
页数：5
相关论文
共 15 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]   DISTRIBUTED RESET [J].
ARORA, A ;
GOUDA, M .
IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (09) :1026-1038
[3]   AN O(M LOG N)-TIME ALGORITHM FOR THE MAXIMAL PLANAR SUBGRAPH PROBLEM [J].
CAI, JZ ;
HAN, XF ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1993, 22 (06) :1142-1162
[4]   SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].
DIJKSTRA, EW .
COMMUNICATIONS OF THE ACM, 1974, 17 (11) :643-644
[5]   A linear-time algorithm for finding a maximal planar subgraph [J].
Djidjev, Hristo N. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (02) :444-462
[6]   A SELF-STABILIZING ALGORITHM FOR COLORING PLANAR GRAPHS [J].
GHOSH, S ;
KARAATA, MH .
DISTRIBUTED COMPUTING, 1993, 7 (01) :55-59
[7]   EFFICIENT PLANARITY TESTING [J].
HOPCROFT, J ;
TARJAN, R .
JOURNAL OF THE ACM, 1974, 21 (04) :549-568
[8]  
Karp B., 2000, MobiCom 2000. Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, P243, DOI 10.1145/345910.345953
[9]   Localized Delaunay triangulation with application in Ad Hoc wireless networks [J].
Li, XY ;
Calinescu, G ;
Wan, PJ ;
Wang, Y .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2003, 14 (10) :1035-1047
[10]  
Liebers A., 2001, Journal of Graph Algorithms and Applications, V5
12