A Fast Algorithm for Optimally Increasing the Edge Connectivity

DOI10.1137/S0097539792234226MaRDI QIDQ4376163zbMATH OpenOpenAlexFDO

Authors Dalit Naor, Dan Gusfield, Chip Martel

Publication date 10 February 1998

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

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

zbMATH Keywords

graph algorithmsnetwork flowgraph connectivityminimum cuts

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• scientific article; zbMATH DE number 1979495
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• scientific article; zbMATH DE number 2080256
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Deterministic Edge Connectivity in Near-Linear Time
• Optimizing algebraic connectivity by edge rewiring
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
• Edge connectivity augmentation in near-linear time
• Parallel and fast sequential algorithms for undirected edge connectivity augmentation
• On optimizing restricted edge connectivity of graphs

Cited in

(31)

• Computing the 4-edge-connected components of a graph: an experimental study
• Augmenting undirected node-connectivity by one
• Minimum degree orderings
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Monte Carlo safeguarding of key links through multiple random walks in large network
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• Structured connectivity augmentation
• A note on minimizing submodular functions
• NA-EDGE-CONNECTIVITY AUGMENTATION PROBLEMS BY ADDING EDGES(<Special Issue>Network Design, Control and Optimization)
• On the Wimer method for designing edge-based algorithms
• A fast algorithm for cactus representations of minimum cuts
• Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
• scientific article; zbMATH DE number 1759470 (Why is no real title available?)
• Triangulating planar graphs while minimizing the maximum degree
• Canonical cactus representation for miminum cuts
• Hypergraph connectivity augmentation in strongly polynomial time
• The common structure of the curves having a same Gauss word
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Approximation algorithms for graph augmentation
• scientific article; zbMATH DE number 3858437 (Why is no real title available?)
• Optimal Mixed Graph Augmentation
• Incrementing bipartite digraph edge-connectivity
• A cactus theorem for end cuts
• A new saling algorithm for the maximum mean cut problem
• Connectivity-faithful graph drawing
• Augmenting trees so that every three vertices lie on a cycle
• Minimizing a monotone concave function with laminar covering constraints
• Successive edge-connectivity augmentation problems
• Augmenting undirected node-connectivity by one
• Deterministic Edge Connectivity in Near-Linear Time
• Parameterized algorithms to preserve connectivity

This page was built for publication: A Fast Algorithm for Optimally Increasing the Edge Connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376163)