A self-stabilizing graph algorithm: Finding the cutting center of a tree

DOI10.1080/00207160310001650062MaRDI QIDQ4464264zbMATH OpenOpenAlexFDO

Authors Hussein Thompson, Pranay Chaudhuri

Publication date 27 May 2004

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160310001650062

zbMATH Keywords

cutting centerdistributed algorithmself-stabilizing algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Review text

A vertex is called cutting center of a tree \(T\) if its removal from \(T\) separates a maximum number of pairs of vertices, see \textit{F. Harary} and \textit{P. J. Slater} [Inf. Process. Lett. 23, 317--319 (1986; Zbl 0624.68058)]. The distributed self-stabilizing algorithm proposed here requires \(O(n^2)\) moves.

Recommendations

• A SELF-STABILIZING DISTRIBUTED ALGORITHM TO FIND THE CENTER OF A TREE GRAPH
• A self-stabilizing algorithm which finds a 2-center of a tree
• A self-stabilizing algorithm for the center-finding problem assuming read/write separate atomicity
• A linear algorithm for the cutting center of a tree
• A self-stabilizing algorithm for finding weighted centroid in trees

Cites work

• A linear algorithm for the cutting center of a tree
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• A self-stabilizing algorithm for detecting fundamental cycles in a graph
• An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components
• Self-stabilization (in spite of distributed control) in tree-structured systems
• Self-stabilizing depth-first search
• Self-stabilizing systems in spite of distributed control

Cited in

(8)

• A self-stabilizing algorithm which finds a 2-center of a tree
• On bounds for the cutting number of a graph
• A self-stabilizing algorithm for finding weighted centroid in trees
• A SELF-STABILIZING DISTRIBUTED ALGORITHM TO FIND THE CENTER OF A TREE GRAPH
• Self-stabilizing Cuts in Synchronous Networks
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• A linear algorithm for the cutting center of a tree
• A self-stabilizing algorithm for cut problems in synchronous networks

This page was built for publication: A self-stabilizing graph algorithm: Finding the cutting center of a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4464264)