A linear algorithm for the cutting center of a tree

Harary, Frank; Slater, Peter J.

1986-11-24

Citation: Harary, Frank, Slater, Peter J. (1986/11/24)."A linear algorithm for the cutting center of a tree." Information Processing Letters 23(5): 317-319. <http://hdl.handle.net/2027.42/25975>

Abstract: 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.

DOIs: http://dx.doi.org/10.1016/0020-0190(86)90093-1

URI: http://www.sciencedirect.com/science/article/B6V0F-482R9JR-2H/2/ae658eee6772198c33b527be31c30ba8

Handle: http://hdl.handle.net/2027.42/25975

Show full item record