
doi: 10.1137/0216041
We consider an augmentation problem on mixed graphs that generalizes and unifies two augmentation problems considered by \textit{K. P. Eswaran} and \textit{R. E. Tarjan} [ibid. 5, 653-665 (1976; Zbl 0346.05112)]. The mixed augmentation problem has applications in the design of communication networks, and forms of mixed augmentation problem are central in statistical data security problems discussed in [Yale Univ. Tech. Report, August 1984]. We solve the augmentation problem on mixed graphs in time linear in the number of edges of the graph, the same time bound obtained in [loc. cit.] for each of the two special cases.
Connectivity, Analysis of algorithms and problem complexity, augmentation problem, strong connectivity, mixed graphs, Directed graphs (digraphs), tournaments, graph orientation
Connectivity, Analysis of algorithms and problem complexity, augmentation problem, strong connectivity, mixed graphs, Directed graphs (digraphs), tournaments, graph orientation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
