first
prev
toc
next
last
Download Citation
Recommend
Mark
Alert
Link
Print
A self-stabilizing graph algorithm: Finding the cutting center of a tree
Authors:
Pranay Chaudhuri a;
Hussein Thompson a
| Affiliation: | a Department of Computer Science, Mathematics and Physics, University of the West Indies, Bridgetown, Barbados |
DOI:
10.1080/00207160310001650062
Publication Frequency:
12 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
81,
Issue
2
February
2004
, pages 183
- 190
International Journal of Computer Mathematics,
Volume
81,
Issue
2
February
2004
, pages 183
- 190
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 12
Formats available:
PDF
(English)
Article Requests:
Order Reprints
:
Request Permissions
-
Single Article Purchase:
US$37.00
-
buy now
-
Sign In
- Online Sample
add to cart 
[ show other buying options ]
View Article:
View Article (PDF)
Abstract
The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G -
 i . The cutting center consists of the set of nodes of G with maximal cutting number. This article presents a self-stabilizing algorithm for finding the cutting numbers for all nodes of a tree T = (VT, ET) and hence the cutting center of T. It is shown that the proposed self-stabilizing algorithm requires O(n2) moves. The algorithm complexity can also be expressed as O(n) rounds.†E-mail: hthompson@uwichill.edu.bb |
| Keywords: Distributed system; Self-stabilizing algorithm; Tree; Cutting center; Complexity |
| view references (12) |
|
Bookmark with:
|
CiteULike
Del.icio.us
BibSonomy
Connotea
More bookmarks
