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

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	518-522
Number of pages	5
Journal	Information Processing Letters
Volume	109
Issue number	10
DOIs	https://doi.org/10.1016/j.ipl.2009.01.013
State	Published - 30 Apr 2009

Keywords

Bipartite graph
Fault tolerance
Planar graph
Self-stabilization
Spanning tree

Access to Document

10.1016/j.ipl.2009.01.013

Cite this

@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

Abstract

Keywords

Access to Document

Fingerprint

Cite this