Minimal k‐arc connected graphs
作者:
D. R. Fulkerson,
L. S. Shapley,
期刊:
Networks
(WILEY Available online 1971)
卷期:
Volume 1,
issue 1
页码: 91-98
ISSN:0028-3045
年代: 1971
DOI:10.1002/net.3230010108
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractA graph is k‐arc‐connected if it is necessary to remove at least k arcs in order to disconnect the graph. This paper solves the problem of determining the least number of arcs required in a k‐arc‐connected graph on n nodes by describing constructions that produce such graphs having kn/2 arcs (for kn éven) or (kn+1) /2 arcs (for kn odd). These results have application to the practical problem of synthesizing minimum cost, “k‐reliable” communic
点击下载:
PDF
(364KB)
返 回