Flexible Graph Connectivity

DOI10.1007/978-3-030-45771-6_2MaRDI QIDQ5041731zbMATH OpenOpenAlexFDO

Authors David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler

Publication date 14 October 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-45771-6_2

zbMATH Keywords

approximation algorithmsconnectivity augmentationnetwork design

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Flexible graph connectivity
• Connection graphs
• scientific article; zbMATH DE number 1539529
• Connectivity parameters of graphs
• Graphs with given connectivity properties
• scientific article; zbMATH DE number 2172752
• Connectivity of path graphs
• scientific article; zbMATH DE number 1744097
• Connected Soft Graph
• Connected graphs and their connectivities

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximation Algorithms for Several Graph Augmentation Problems
• Beating approximation factor two for weighted tree augmentation with bounded costs
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
• Bulk-robust combinatorial optimization
• Flexible graph connectivity
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Improved approximation for tree augmentation: saving by rewiring
• Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
• LP-relaxations for tree augmentation
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• Time-expanded packings

Cited in

(3)

• Flexible graph connectivity
• Improved approximations for relative survivable network design
• An O( n)-approximation algorithm for (p, q)-flexible graph connectivity via independent rounding

This page was built for publication: Flexible Graph Connectivity

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