Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity

DOI10.1137/20M1361857MaRDI QIDQ5883291zbMATH OpenFDO

Authors Hiroshi Hirai, Motoki Ikeda

Publication date 30 March 2023

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

Full work available at URL https://arxiv.org/abs/2008.10052

zbMATH Keywords

discrete convex analysisnode-connectivityseparately capacitated multiflowterminal backup problem

Mathematics Subject Classification ID

Flows in graphs (05C21) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• The generalized terminal backup problem
• The generalized terminal backup problem
• A dual descent algorithm for node-capacitated multiflow problems and its applications

Cites work

• L-convexity on graph structures
• A cost-scaling algorithm for computing the degree of determinants
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• A dual descent algorithm for node-capacitated multiflow problems and its applications
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Discrete Convex Analysis
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Graphs of some CAT(0) complexes
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Minimum cost multiflows in undirected networks
• Network design via iterative rounding of setpair relaxations
• On some connectivity properties of Eulerian graphs
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• Terminal backup, 3D matching, and covering cubic graphs
• The generalized terminal backup problem
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(4)

• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• The generalized terminal backup problem
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• The generalized terminal backup problem

This page was built for publication: Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity

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