A linear algorithm for the cutting center of a tree

DOI10.1016/0020-0190(86)90093-1MaRDI QIDQ578919zbMATH OpenOpenAlexFDO

Authors Peter Slater, Frank Harary

Publication date 1986

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2027.42/25975

zbMATH Keywords

connected graphcutting numberlinear algorithm

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10)

Review text

As a measure of the extent to which the removal of a node disconnects a graph, the cutting number c(v) of a node v in a connected graph G has been defined to be the number of pairs of nodes in different components of G-\(\{\) \(v\}\). We present a linear algorithm for determining c(v) for all nodes of a tree, and hence for identifying the cutting center, which consists of the nodes v at which c(v) is maximized.

Recommendations

• A self-stabilizing graph algorithm: Finding the cutting center of a tree
• On bounds for the cutting number of a graph
• scientific article; zbMATH DE number 4095237
• On finding fundamental cut sets
• scientific article; zbMATH DE number 2104823

Cites work

• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Parallel concepts in graph theory
• The cutting center theorem for trees

Cited in

(7)

• The expected number of pairs of connected nodes: Pair-connected reliability
• Cutting numbers for the forward loop backward hop network
• On bounds for the cutting number of a graph
• INDUCTIVE ALGORITHMS ON FINITE TREES
• A self-stabilizing graph algorithm: Finding the cutting center of a tree
• scientific article; zbMATH DE number 2104823 (Why is no real title available?)
• A linear algorithm for finding the k‐broadcast center of a tree

This page was built for publication: A linear algorithm for 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 Q578919)