Approximation algorithms for graph augmentation

DOI10.1007/3-540-55719-9_85MaRDI QIDQ5204328zbMATH OpenOpenAlexFDO

Authors Samir Khuller, Ramakrishna Thurimella

Publication date 4 December 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55719-9_85

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation Algorithms for Graph Augmentation
• Approximation algorithms for vertex-connectivity augmentation on the cycle
• Approximation algorithms for connectivity augmentation problems
• Combinatorics and algorithms for augmenting graphs
• Approximation algorithms for graph approximation problems
• The parametric complexity of graph diameter augmentation
• Approximating Node-Connectivity Augmentation Problems
• Approximating node-connectivity augmentation problems
• scientific article; zbMATH DE number 2080256
• scientific article; zbMATH DE number 1979724

Cites work

• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• An application of submodular flows
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmentation Problems
• Biconnectivity approximations and graph carvings
• Edge-connectivity augmentation problems
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Matroid Intersection
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Smallest Augmentations to Biconnect a Graph

Cited in

(13)

• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• A note on optimal covering augmentation for graphic polymatroids.
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation
• Approximation Algorithms for Graph Augmentation
• scientific article; zbMATH DE number 1979495 (Why is no real title available?)
• scientific article; zbMATH DE number 1979724 (Why is no real title available?)
• scientific article; zbMATH DE number 2081003 (Why is no real title available?)
• scientific article; zbMATH DE number 1759470 (Why is no real title available?)
• scientific article; zbMATH DE number 1760036 (Why is no real title available?)
• scientific article; zbMATH DE number 1833404 (Why is no real title available?)
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• On finding augmenting graphs

This page was built for publication: Approximation algorithms for graph augmentation

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