The Generalized Terminal Backup Problem

DOI10.1137/140972858zbMath1330.90090OpenAlexW1412689292MaRDI QIDQ2947440

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

polynomial-time algorithmconnectivity augmentation problemsurvivable network design problemskew-supermodular function

Mathematics Subject Classification ID

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

Related Items (4)

Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering symmetric supermodular functions by uniform hypergraphs
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Local edge-connectivity augmentation in hypergraphs is NP-complete
• Edge-connectivity augmentation problems
• Über die Maximalzahl kantendisjunkter A-Wege
• Augmenting hypergraphs by edges of size two
• Covering symmetric supermodular functions by graphs
• Hypergraph connectivity augmentation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A unifying approach to splitting-off
• Covering symmetric semi-monotone functions
• A Survey on Covering Supermodular Functions
• Edge-Connectivity Augmentations of Graphs and Hypergraphs
• Terminal Backup, 3D Matching, and Covering Cubic Graphs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• On some connectivity properties of Eulerian graphs
• NA-EDGE-CONNECTIVITY AUGMENTATION PROBLEMS BY ADDING EDGES(<Special Issue>Network Design, Control and Optimization)
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• The Generalized Terminal Backup Problem
• Integer Programming and Combinatorial Optimization

This page was built for publication: The Generalized Terminal Backup Problem