IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E96D(3) 426-432 2013年3月 [査読有り]
PREMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n(8)) time algorithm for PREIMAGE CONSTRUCTION on pe...
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7276 248-259 2012年 [査読有り]
We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the ...
Discrete Math., Alg. and Appl. 4(3) 1250039-1250039 2012年 [査読有り]
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs...
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E94D(6) 1185-1189 2011年6月 [査読有り]
The Voronoi game is a two-person perfect information game modeling a competitive facility location. The original version of the game is played on a continuous domain. Only two special cases (1-dimensional case and I-round case) have been extensive...
Jean Cardinal   Erik D. Demaine   Martin L. Demaine   Shinji Imahori   Tsuyoshi Ito   Masashi Kiyomi   Stefan Langerman   Ryuhei Uehara   Takeaki Uno   
GRAPHS AND COMBINATORICS 27(3) 341-351 2011年5月 [査読有り]
How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple...