Approximation algorithms for graph augmentation

DOI10.1007/3-540-55719-9_85zbMath1425.68315OpenAlexW1611628598MaRDI QIDQ5204328

Ramakrishna Thurimella, Samir Khuller

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

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

Cites Work

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

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