5 papers
Minmax Regret 1-Sink Location Problems on Dynamic Flow Path Networks with Parametric Weights
Tetsuya Fujie, Yuya Higashikawa, Naoki Katoh +2
This paper addresses the minmax regret 1-sink location problem on dynamic flow path networks with parametric weights. We are given a dynamic flow network consisting of an undirecte…
Almost Linear Time Algorithms for Minsum -Sink Problems on Dynamic Flow Path Networks
Yuya Higashikawa, Naoki Katoh, Junichi Teruyama +1
We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capaci…
On Computing a Center Persistence Diagram
Yuya Higashikawa, Naoki Katoh, Guohui Lin +4
Throughout this paper, a persistence diagram is composed of a set of planar points (each corresponding to a topological feature) above the line , as well as the…
Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms
Kazuo Iwama, Junichi Teruyama, Shuntaro Tsuyama
The problem called "String reconstruction from substrings" is a mathematical model of sequencing by hybridization that plays an important role in DNA sequencing. In this problem, w…
Improved Average Complexity for Comparison-Based Sorting
Kazuo Iwama, Junichi Teruyama
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is . For many ef…