18 citations · 32 across the 11 of their papers we have counts for
12 papers
The Complexity of Boolean Connectivity Problem of -Horn Formulas
Takashi Horiyama, Shoon Mineyoshi, Yuto Okura +2
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the -dimensional hypercube. This problem…
Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
Kosuke Susukita, Junichi Teruyama
Proving the NP-completeness of pencil-and-paper puzzles typically relies on reductions from combinatorial problems such as the satisfiability problem (SAT). Although the properties…
Sink Location Problems in Dynamic Flow Grid Networks
Yuya Higashikawa, Ayano Nishii, Junichi Teruyama +1
A dynamic flow network consists of a directed graph, where nodes called sources represent locations of evacuees, and nodes called sinks represent locations of evacuation facilities…
Faster Algorithms for Evacuation Problems in Networks with the Single Sink of Small Degree
Yuya Higashikawa, Naoki Katoh, Junichi Teruyama +1
In this paper, we propose new algorithms for evacuation problems defined on dynamic flow networks. A dynamic flow network is a directed graph in which source nodes are given suppli…
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
Takehiro Ito, Jun Kawahara, Yu Nakahata +4
This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In g…
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…
Reconstructing Strings from Substrings with Quantum Queries
Richard Cleve, Kazuo Iwama, François Le Gall +4
This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, t…
Quantum Counterfeit Coin Problems
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only ``balanced'' or `…