摘要
本文研究了以最小边集扩充一个任意有向图为K边连通有向图这一优化问题。提出了一个复杂度o(|V|5)的有效算法。该算法为可靠网络的计算机辅助设计打下了基础。
The optimization problem of constructing a K-edge-connected directed graph from any given directed graph by adding a minimum set of edges is studied. An efficient algorithm with complexity of O(|V|5) is presented. This algorithm contributes a foundation for the computer aided design of reliable networks.
基金
国家自然科学基金
关键词
图论
有向图
K边连通
Graph theory
Directed graph
K-edge-connected directed graph
