A near optimal algorithm for vertex connectivity augmentation

DOI10.1007/3-540-40996-3_27MaRDI QIDQ4472504zbMATH OpenFDO

Authors Bill Jackson, Tibor Jordán

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1969/19690313.htm

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Independence free graphs and vertex connectivity augmentation
• Independence free graphs and vertex connectivity augmentation
• A note on the vertex-connectivity augmentation problem
• On the minimum augmentation of an -connected graph to a k-connected graph
• Connectivity augmentation of graphs

Cited in

(26)

• Directed vertex-connectivity augmentation
• A note on the vertex-connectivity augmentation problem
• Independence free graphs and vertex connectivity augmentation
• The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
• A 4+ approximation for k-connected subgraphs
• Property testing on \(k\)-vertex-connectivity of graphs
• Approximating node-connectivity augmentation problems
• Augmenting forests to meet odd diameter requirements
• Simpler and faster vertex connectivity augmentation algorithms. (Extended abstract)
• A unified framework for bi(tri)connectivity and chordal augmentation
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation
• NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
• Tri-connectivity augmentation in trees
• An Efficient Vertex Addition Method for Broadcast Networks
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• Independence free graphs and vertex connectivity augmentation
• Structured connectivity augmentation
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Structured connectivity augmentation
• Approximation algorithms for graph augmentation
• Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
• Node connectivity augmentation via iterative randomized rounding
• Tight approximation algorithm for connectivity augmentation problems

This page was built for publication: A near optimal algorithm for vertex connectivity augmentation

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