Approximation algorithms for graph augmentation

DOI10.1007/3-540-55719-9_85zbMATH Open1425.68315OpenAlexW1611628598MaRDI QIDQ5204328FDOQ5204328

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• A note on optimal covering augmentation for graphic polymatroids.
• Title not available (Why is that?)
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• On finding augmenting graphs
• Title not available (Why is that?)
• Approximation Algorithms for Graph Augmentation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation

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)