A linear algorithm for the cutting center of a tree (Q578919)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear algorithm for the cutting center of a tree |
scientific article |
Statements
A linear algorithm for the cutting center of a tree (English)
0 references
1986
0 references
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.
0 references
cutting number
0 references
connected graph
0 references
linear algorithm
0 references
