Distributed edge coloration for bipartite networks

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/28065

Title:	Distributed edge coloration for bipartite networks
Authors:	Huang,ST;Tzeng,CH
Contributors:	光電科學研究所
Keywords:	SYSTEMS;TIME;STABILIZATION;MULTIGRAPHS;ALGORITHMS;GRAPHS
Date:	2009
Issue Date:	2010-06-29 19:41:09 (UTC+8)
Publisher:	中央大學
Abstract:	This paper presents a self-stabilizing algorithm to color the edges of a bipartite network such that any two adjacent edges receive distinct colors. The algorithm has the self-stabilizing property; it works without initializing the system. It also works in a de-centralized way without a leader computing a proper coloring for the whole system. Moreover, it finds an optimal edge coloring and its time complexity is O(n (2) k + m) moves, where k is the number of edges that are not properly colored in the initial configuration.
Relation:	DISTRIBUTED COMPUTING
Appears in Collections:	[Graduate Institute of Optics and Photonics] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	465	View/Open

社群 sharing