Approximating Minimum Cost Connectivity Orientation and Augmentation

DOI10.1137/15100583XzbMath1387.68138WikidataQ130208284 ScholiaQ130208284MaRDI QIDQ4606698

Mohit Singh, László A. Végh

Publication date: 9 March 2018

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

zbMATH Keywords

graph algorithmsgraph connectivityapproximation algorithmsgraph orientation

Mathematics Subject Classification ID

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

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Edge-connectivity augmentation problems
• On the orientation of graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Combined connectivity augmentation and orientation problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Iterative Methods in Combinatorial Optimization
• On the Problem of Decomposing a Graph into n Connected Factors
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Hypergraphic LP Relaxations for Steiner Trees
• Robbins's Theorem for Mixed Multigraphs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Biconnectivity approximations and graph carvings
• Directed Network Design with Orientation Constraints
• Steiner Forest Orientation Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating Minimum Cost Connectivity Orientation and Augmentation