OPTIMAL MIXED GRAPH AUGMENTATION

被引：16

作者：

GUSFIELD, D

机构：

[1] Univ of California, Davis, CA, USA, Univ of California, Davis, CA, USA

来源：

SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 04期

关键词：

COMPUTER NETWORKS - Design - DATA PROCESSING - Security of Data;

D O I：

10.1137/0216041

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we consider an augmentation problem on mixed graphs that generalizes and unifies two augmentation problems considered by K. P. Eswaran and R. E. Tarjan. The mixed augmentation problem has applications in the design of communication networks, and forms of the mixed augmentation problem are central in certain statistical data security problems. We solve the augmentation problem on mixed graphs in time linear in the number of edges of the graph.

引用

页码：599 / 612

页数：14

共 9 条

[1] ROBBINS THEOREM FOR MIXED MULTIGRAPHS [J].