Augmentation Problems

DOI10.1137/0205044zbMath0346.05112MaRDI QIDQ4115167

Robert Endre Tarjan, Kapali P. Eswaran

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0205044

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C99: Graph theory

Related Items

Augmenting trees so that every three vertices lie on a cycle, An approximation algorithm for minimum-cost vertex-connectivity problems, Graph connectivity and its augmentation: Applications of MA orderings, On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, A linear time algorithm for computing 3-edge-connected components in a multigraph, A minimum 3-connectivity augmentation of a graph, Faster approximation algorithms for weighted triconnectivity augmentation problems, Communication complexity of fault-tolerant information diffusion, Triangulating planar graphs while minimizing the maximum degree, Determination of social laws for multi-agent mobilization, Evolutionary local search for the edge-biconnectivity augmentation problem, Increasing digraph arc-connectivity by arc addition, reversal and complement, Independence free graphs and vertex connectivity augmentation, An analogue of Hoffman's circulation conditions for max-balanced flows, A smallest augmentation to 3-connect a graph, On the minor-minimal 2-connected graphs having a fixed minor, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Two-page book embedding of trees under vertex-neighborhood constraints, Multigraph augmentation under biconnectivity and general edge-connectivity requirements