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

Chi Hung Tzeng; Jehn Ruey Jiang; Shing Tsaan Huang

doi:10.1016/j.ipl.2009.01.013

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

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang

資訊工程學系

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

摘要

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 2 n - 4 edges in O (n) rounds, where n is the number of nodes.

原文	???core.languages.en_GB???
頁（從 - 到）	518-522
頁數	5
期刊	Information Processing Letters
卷	109
發行號	10
DOIs	https://doi.org/10.1016/j.ipl.2009.01.013
出版狀態	已出版 - 30 4月 2009

存取文件

10.1016/j.ipl.2009.01.013

引用此

@article{7446d9690b8e40198ea21bee483800b7,

title = "A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks",

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 2 n - 4 edges in O (n) rounds, where n is the number of nodes.",

keywords = "Bipartite graph, Fault tolerance, Planar graph, Self-stabilization, Spanning tree",

author = "Tzeng, {Chi Hung} and Jiang, {Jehn Ruey} and Huang, {Shing Tsaan}",

year = "2009",

month = apr,

day = "30",

doi = "10.1016/j.ipl.2009.01.013",

language = "???core.languages.en_GB???",

volume = "109",

pages = "518--522",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "10",

}

TY - JOUR

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

AU - Tzeng, Chi Hung

AU - Jiang, Jehn Ruey

AU - Huang, Shing Tsaan

PY - 2009/4/30

Y1 - 2009/4/30

N2 - 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 2 n - 4 edges in O (n) rounds, where n is the number of nodes.

AB - 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 2 n - 4 edges in O (n) rounds, where n is the number of nodes.

KW - Bipartite graph

KW - Fault tolerance

KW - Planar graph

KW - Self-stabilization

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=62549095852&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.01.013

DO - 10.1016/j.ipl.2009.01.013

M3 - 期刊論文

AN - SCOPUS:62549095852

SN - 0020-0190

VL - 109

SP - 518

EP - 522

JO - Information Processing Letters

JF - Information Processing Letters

IS - 10

ER -

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

摘要

存取文件

指紋

引用此