Masashi Kiyomi

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 states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. This article is a technical report without peer review, and its polished version will be published elsewhere.

電波による通信を用いたサービスでは、基地局の通信の範囲は円となる．複数の基地局からの通信が重なることで不具合がでる場合もあり，どのように基地局を配置するかが問題になる．ここでサービスの利用者を点，電波の届く範囲を単位円としたときに，重なりの無い単位円集合ですべての点を覆えるか，という問題が考えられる．本研究では，これを複数の単位円による点集合の排他的被覆問題として取り扱う．どのように配置しても必ず適当に配置した単位円の集合で排他的に被覆できる点の個数 k は 1 以上で上限があり，既知の結果として 10≦k<108 が知られている．本研究では，この上界を改善することを目的とし，提案手法により 10≦k<54 と改善することができた．In services using the electric wave communication, the range of the electric wave from a base station becomes a circle. The situation where two ranges of the wave intersect can be problematic. Therefore, base station layout becomes a problem. Consider 2 points in the plane. Clearly we can cover them by disjoint unit disks. It is known that any 10 points can be covered by some disjoint unit disks, and carefully arranged 108 points cannot be covered by any arrangement of unit disks. We improve the upper bound from 108 to 54, i.e. we show an arrangement of 54 points which cannot be covered by any arrangement of unit disks.

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 1-round case) are well investigated. Recently, the discrete Voronoi game of which the game arena is given as a graph was introduced. In this note, we give a complete analysis of the discrete Voronoi game on a path.

We introduce a new origami problem about pleats foldings. For a given assignment of n creases of mountains and valleys, we make a strip of paper well-creased according to the assignment at regular intervals. We assume that (1) paper has 0 thickness and some layers beneath a crease can be folded simultaneously, (2) each folded state is flat, (3) each crease remembers its last folded state made at the crease, and (4) the paper is rigid except at the n given creases. On this model, we aim to find efficient ways of folding a given mountain-valley assignment. We call this problem unit folding problem for general patterns, and pleats folding problem when the mountain-valley assignment is "MV MV MV…." The complexity is measured by the number of foldings and the cost of unfoldings is ignored. Trivially, we have an upper bound n and a lower bound log(n+1). We first give some nontrivial upper bounds: (a) any mountain-valley assignment can be made by 「n/2」+「log(n+1)」 foldings, and (b) a pleats folding can be made by O(n^ε) foldings for any ε>0. Next, we also give a nontrivial lower bound: (c) almost all mountain-valley assignments require Ω(n/(log n)) foldings. The results (b) and (c) imply that a pleats folding is easy in the unit folding problem.

コーダルグラフは,統計学,数値計算法,最適化算法などの諸分野において,効率的な計算を行うことができる非常に重要なグラフクラスである.統計学においては,コーダルグラフはグラフィカルモデルが分解可能であるための必要十分条件として知られる.本稿では「コーダルグラフサンドイッチ問題」を取り扱う.コーダルグラフサンドイッチ問題は,包含関係にあるグラフの対が与えられたとき,そのグラフに挟まれるコーダルグラフを探索する問題である.コーダルグラフサンドイッチ問題は一般にはNP完全問題である.本稿では特に,与えられるグラフの対の一方がコーダルである場合を考え,サンドイッチされるコーダルグラフの効率的な生成法について議論する.また,これらの応用について述べる.

A graph is chordal iff its vertices do not induce any chordless cycle of length more than three. Given a graph G and G (where G is a subgraph of G), the problem to find a graph G such that G is a proper subgraph of G and G is a proper subgraph of G is known as "chordal graph sandwich problem" and is NP-hard. We show that if either G or G is chordal, we can solve the chordal graph sandwich prolem in polynomial time. Besides, we develop an algorithm for enumerating every graph G that is a subgraph of G and a super graph of G, under the condition that at least one of G and G is chordal. This result is a natural extension of our previous work [5].