A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks |
| |
| Authors: | Chi-Hung Tzeng Shing-Tsaan Huang |
| |
| Affiliation: | a Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan
b Department of Computer Science and Information Engineering, National Central University, Jhongli, Taiwan |
| |
| Abstract: | 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. |
| |
| Keywords: | Bipartite graph Fault tolerance Planar graph Self-stabilization Spanning tree |
| 本文献已被 ScienceDirect 等数据库收录！ |
