清見 礼

不完全なデータが与えられたときに,形質に基づいて系統樹を復元する問題を研究する.より正確には,形質が二値であり,有向完全系統樹の仮定が成り立つ場合に,ある種に対してある形質の状態がデータとして失われている状況を考える.本研究の目的は失われたデータを補完したときに得られる完全系統樹をすべて列挙するための効率的アルゴリズムを設計することである.単純な分枝限定アルゴリズム(B&B)は理論的に良い計算量を持つが,ゼロサプレス型二分決定グラフ(ZDD)に基づく別の方法を提案する.ランダム生成されたデータに対する実験では,ZDDに基づく手法がB&Bよりも優れた結果を示した.また,与えられた不完全データと矛盾しない完全系統樹の数を計算する問題が#P完全であることを示し,すなわち,効率的標本抽出が難しいことの傍証を与える.

電波による通信を用いたサービスでは、基地局の通信の範囲は円となる．複数の基地局からの通信が重なることで不具合がでる場合もあり，どのように基地局を配置するかが問題になる．ここでサービスの利用者を点，電波の届く範囲を単位円としたときに，重なりの無い単位円集合ですべての点を覆えるか，という問題が考えられる．本研究では，これを複数の単位円による点集合の排他的被覆問題として取り扱う．どのように配置しても必ず適当に配置した単位円の集合で排他的に被覆できる点の個数 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.

ボロノイゲームは競合施設配置をモデル化した二人完全情報ゲームである.このゲームはもともと連続した領域上で考えられおり,その場合,1次元上の場合と,1ラウンドの場合については結論が出ている.最近,グラフ上で行なう離散ボロノイゲームが提案された.本研究ではパス上の離散ボロノイゲームに関して,完全な解析を行なう.

PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals in the algorithmic aspects of the conjecture. We present an O(n6) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs. A simplified algorithm can be applied for PREIMAGE CONSTRUCTION on distancehereditary graphs. There are polynomial time isomorphism algorithms for permutation graphs. However the number of permutation graphs obtained by adding a vertex to a permutation graph may be exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals in the algorithmic aspects of the conjecture. We present an O(n6) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs. A simplified algorithm can be applied for PREIMAGE CONSTRUCTION on distancehereditary graphs. There are polynomial time isomorphism algorithms for permutation graphs. However the number of permutation graphs obtained by adding a vertex to a permutation graph may be exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.

本稿では 「じゃばら折り」 に関する新しい折り紙の問題を提案する．本問題では与えられた ｎ 個の山折り／谷折りの割り当てに対して，紙をその割り当てに従って等間隔に折ることを目的とする．扱う紙のモデルは以下の通り． （1） 紙は厚み 0 で重ねて一度に複数枚折ることができる． （2） それぞれの折り状態は平坦である． （3） それぞれの折り目はそこで最後に折られたときの折り状態を記憶する． （4） 紙は ｎ 箇所の折り目を除いて剛体である．このモデルにおいて，与えられた割り当てを実現する効率の良い折り操作を見つけることがこの問題の目的である．一般の山谷割り当てに対する問題を単位長折り問題と呼び，山谷割り当てが 「MV MV MV ．．．」という形をしているときは特にじゃばら折り問題と呼ぶことにする．アルゴリズムの複雑さは折りの回数によって測り，折りを開く回数は無視する．この問題には自明な上界、と自明な下界 log （n + 1） が存在する．本稿ではまず以下の非自明な 2 つの上界を示す． （a） どんな山谷割り当てでも高々 [n／2] ＋ [log (n＋1)] 1 回の折りで実現することができる． （b) 任意の ∊＞0 に対してじゃばら折りは 0 （n∊） 回の折りで実現することができる．次に以下の非自明な下界を示す． （c） ほとんどすべての山谷割り当ては Ω （n／log n） 回折らなければ作ることができない結果 （b） と （c） より，じゃばら折り問題は単位長折り問題の中では簡単な部類に入ることがわかった．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 "MVMVMV…" 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 Ω(log n / n) foldings. The results (b) and (c) imply that a pleats folding is easy in the unit folding problem.

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

コーダルグラフは大きさが4以上の誘導部分サイクルをもたないグラフとして定義される。グラフGとGの部分グラフGが与えられた時、Gの真部分グラフでかつGを真部分グラフとして持つようなコーダルグラフGをみつける問題は、コーダルグラフサンドイッチ問題と呼ばれ、NP-困難であることが知られている。我々は、GまたはGがコーダルグラフであれば、コーダルグラフサンドイッチ問題は容易に解くことが可能であることを示した。さらに、これを用いてGおよびGのいずれか一方がコーダルである場合に、Gの部分グラフであり、Gを部分グラフとして持つようなコーダルグラフをすべて列挙する問題のアルゴリズムを開発した。この結果は、著者らの以前の結果[5]の自然な拡張になっている。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 polem in polynomial time. Resides, we develop an algotithm 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].