著者

KAWARABAYASHI Ken-ichi

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.104, no.339, 2004-10-08

---

We shall survey recent progress on algorithm aspect of graph minor theory. One of the main results on Graph Minor Project by Robertson and Seymour is the following. Given a graph G and p pairs of vertices of G for fixed p, there is a polynomial time (actually O(n^3) algorithm to decide if there are p mutually disjoint paths of G linking the pair. If p is part of the input of the problem, then this is one of Karp's NP-complete problems, and it remains NP-complete even for planar graphs. We shall first sketch the algorithm, and explain why the correctness needs * 500 pages to prove. Then we shall focus on applications of this result. Topics include tree-width for planar graphs, 2-path problem (2-linked graph), the odd disjoint cycles, the parity paths problems, Kuratowski's theorem for general surface, nearly-k-bipartite graph problem and algorithm aspect of Hadwiger's conjecture.

著者

山口 一章 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.273, pp.39-42, 2005-09-08

---

頂点に重みがつけられた無向グラフが与えられたとき, 頂点の重みの和が最大となるクリークを求める問題は最大重みクリーク問題と呼ばれている.最大重みクリーク問題の厳密解を分枝限定法によって求める場合, 最大重みクリークの重みの, よりタイトな上界を高速に計算することが重要である.分枝限定法に基づく厳密解法の一つに, ある頂点系列により作成された有向グラフ上の最長経路を求め, それを上界計算に利用する方法がある.本稿は, より良い頂点系列を構成する方法を提案する.計算機実験により提案手法の有効性を検証する.

著者

山口 一章 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.7, pp.1-4, 2005-04-11

---

頂点に重みが付けられた無向グラフが与えられたときに最大重みクリークを求めよという最適化問題は最大重みクリーク問題と呼ばれている. 最大重みクリーク問題の解法としては分枝限定法によるものが知られている. 分枝限定法において計算時間を短縮するためには, タイトな上界をできるだけ短い時間で計算することが重要である. 本稿では, 高速かつ単純な最大重みクリークの上界計算法を提案し, その有効性を実験的に検証する.

著者

市川 龍治 山本 博章

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.708, pp.41-48, 2002-03-05

---

本論文では,拡張正則表現に対する文字列照合問題を扱う。すなわち,長さmの拡張正則表現rと長さnのテキストxが与えられたとき,xの中にrと一致する文字列が存在するかどうか判定する問題である。山本の認識アルゴリズムを利用することによってこの問題を簡単にO(mn^2 +kn^3)時間かつO(mn+kn^2)領域で解くことができる。ここでは,このアルゴリズムを非決定性有限オートマトンおよび決定性有限オートマトンを使って実装することにより,その効率さについて実験的に評価する。

著者

山本 博章

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.59-66, 2005-05-13

---

拡張正規表現に向けた照合アルゴリズムとして, 与えられた拡張正規表現を正規表現に分割し, 各正規表現をNFAに変換することによって照合を行うオートマトン型のアルゴリズムが提案されている.正規表現からNFAを得るための方法はいくつか提案されてるが, 本論文は, オートマトンに基づいた拡張正規表現照合アルゴリズムをいろいろなNFAに対応可能なように修正し, それぞれのNFAによってアルゴリズムの性能がどうのように変わるかを実験的に評価した.特に, Thompsonオートマトン, Glushkovオートマトン, Followオートマトンについて実際に実装し, その性能を調べた.

著者

山本 博章 宮崎 敬

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.127, pp.85-92, 2007-06-22

---

正規表現はコンピュータサイエンスの分野で広く利用されている。本論文では、正規表現に共通集合演算および補集合演算を加えた拡張正規表現(EREと略す)の所属問題および検索問題を扱う。所属問題は、アルファベットΣ上のEREr及び記号列xが与えられたとき、x∈L(r)かどうかを判定する問題である。また、検索問題は、xからy∈L(r)なるすべての部分列yを見つけ出す問題である。ここで、L(r)はL(r)によって表される言語を意味する。そのとき、我々はO(n^2(k_12^H+(k-k_1)⌈n/log n⌉)時間かつO(n(k_12^H+(k-k_1)⌈n/log n⌉)領域で所属問題を解くアルゴリズムを与える。さらに、このアルゴリズムを拡張して、同程度の計算量で検索問題を解くことができることも示す。ここで、nはxの長さ、kはrに出現する共通集合演算及び補集合演算(これらを拡張演算子と呼ぶ)の数を表し、その内k_1は、我々が良性と呼ぶある条件を満たす拡張演算子の数である。また、HはH=max{m_j|m_jはrのj番目のモジュールに出現するΣの記号と拡張演算子の数}と定義する。

著者

飯田 栄治 下平 博 木村 正行

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.94, no.354, pp.51-60, 1994-11-18

被引用文献数

1 2

---

8パズル及び一回り大きくした15パズルについて、探索に基づいた解法がこれまでいくつか研究されている。通常、これらのパズルの探索による解法では、ゴール状態までの手数が少し長くなると容易には解けない。また、効率良い探索を行なうためにヒューリスティック関数を考案することも一般に難しい。そこで、今回は8パズルに対し、探索ではなく問題をいくつかの小問題に分割しそれらの各サブゴールに到達するための整列戦略に従って、状態遷移オペレータを次々に適用することにより高速に問題を解決する手法を提案する。また、いくつか例題に対し代表的な探索方法と比較実験を行なったのでその結果を報告する。

著者

西村 晃一 藤本 典幸 萩原 兼一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.100, no.705, pp.41-48, 2001-03-09

---

現在,我々はタスクスケジューリングを用いて並列プログラムを自動生成する研究を行っている.これまで我々は,分散メモリ型並列計算機の通信特性を考慮し,通信の一括化を行いやすいバルク同期スケジュールを生成するアルゴリズムBCSHを開発してきた.BCSHでは,タスク数が増大するにつれスケジューリングに要する時間が著しく増大する.本研究では,大規模なタスクグラフを扱うために,タスクグラフを分割し並列にスケジューリングするアルゴリズムPBCSHを提案する.PBCSHはバルク同期スケジュールを生成する.PBCSHを評価した結果,PBCSHはBCSHが生成するスケジュールと性能差を小さく抑えつつ短時間でスケジュールを生成でき,またBCSHよりタスク数の多いグラフのスケジューリングができることがわかった.