The generalized terminal backup problem

DOI10.1137/140972858MaRDI QIDQ2947440zbMATH OpenOpenAlexFDO

Authors Attila Bernáth, Yusuke Kobayashi, Tatsuya Matsuoka

Publication date 23 September 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/32de652889ad64efa60ca397da0589399df37556

zbMATH Keywords

connectivity augmentation problempolynomial-time algorithmskew-supermodular functionsurvivable network design problem

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• The generalized terminal backup problem
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Terminal backup, 3D matching, and covering cubic graphs

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Survey on Covering Supermodular Functions
• A unifying approach to splitting-off
• Approximating connectivity augmentation problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmenting hypergraphs by edges of size two
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Covering symmetric semi-monotone functions
• Covering symmetric supermodular functions by graphs
• Covering symmetric supermodular functions by uniform hypergraphs
• Edge-connectivity augmentation problems
• Edge-connectivity augmentations of~graphs~and~hypergraphs
• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• Hypergraph connectivity augmentation
• Integer Programming and Combinatorial Optimization
• Local edge-connectivity augmentation in hypergraphs is NP-complete
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• NA-EDGE-CONNECTIVITY AUGMENTATION PROBLEMS BY ADDING EDGES(<Special Issue>Network Design, Control and Optimization)
• On some connectivity properties of Eulerian graphs
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• Terminal backup, 3D matching, and covering cubic graphs
• The generalized terminal backup problem
• Über die Maximalzahl kantendisjunkter A-Wege

Cited in

(10)

• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Terminal backup, 3D matching, and covering cubic graphs
• Optimal sequential backup strategy under constrained resources
• Discrete convex functions on graphs and their algorithmic applications
• A network design problem with two-edge matching failures
• The generalized terminal backup problem
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Improved approximation algorithms for minimum power covering problems
• Node-connectivity terminal backup, separately-capacitated multiflow, and discrete convexity

This page was built for publication: The generalized terminal backup problem

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