3 papers
cs.DS2020
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity
Hiroshi Hirai, Motoki Ikeda
The terminal backup problems (Anshelevich and Karagiozova (2011)) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to…
cs.DS2020
A cost-scaling algorithm for computing the degree of determinants
Hiroshi Hirai, Motoki Ikeda
In this paper, we address computation of the degree of Dieudonné determinant of \[ A = \sum_{k=1}^m A_k x_k t^{c_k}, \] where ar…
cs.DS2019
A Cost-Scaling Algorithm for Minimum-Cost Node-Capacitated Multiflow Problem
Hiroshi Hirai, Motoki Ikeda
In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-tim…