- 著者
- 富田 悦次 今松 憲一 木幡 康弘 若月 光夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)
- 巻号頁・発行日
- vol.79, no.1, pp.1-8, 1996-01-25
- 被引用文献数
- 13
本論文では, 無向グラフ中の最大クリークを抽出するための単純で効率の良い分枝限定アルゴリズムを提唱する. ここで, いかにして分枝の制限を強力に働かせて解の探索領域を小さくするかが, アルゴリズムの効率化の重要な指標となる. しかし, その分校制限実現のために要する処理時間をできるだけ小さく抑える必要がある. そこで本論文では, その両者の兼合いを適切に達成した, 非常に単純で巧妙な逐次近似彩色-整列法を考案し, それにより探索の各段階において見出し得る最大クリークの上界を得て分技制限を効果的に実現し, 総実行時間も小さく抑えることに成功した. 本アルゴリズムは, 他のいくつかの代表的アルゴリズムと直接実験的比較, あるいは論文上の数値比較により, それらに対して600節点以内の広い範囲の多くのランダムグラフおよび1000節点のいくつかのランダムグラフについて, より高速であることを確認した.
1 0 0 0 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
- 著者
- 中西 裕陽 富田 悦次 若月 光夫 西野 哲朗
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:09135685)
- 巻号頁・発行日
- vol.2014, no.14, pp.1-8, 2014-06-06
NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.
1 0 0 0 OA 形式言語の効率的学習アルゴリズムの開発及びその応用システムの構築
決定性プッシュダウン変換器のスタック記号を1種類に限定した決定性限定1カウンタ変換器について,それが最終状態受理式の場合,より一般的なε-推移を持つ場合についてもその等価性判定及び包含性判定が多項式時間で行えることを明らかにした.また,実時間最終状態受理式決定性限定1カウンタ変換器に対して,所属性質問及び等価性質問を用いた多項式時間の学習アルゴリズムを開発した.更に,正則言語の部分クラスに対する正例からの極限同定を組み込んだジュウシマツの歌構造解析ツールEUREKAを利用することによって,コンピュータ上でトランプゲームの大貧民の対戦を行うプログラムの挙動の規則性が抽出可能なことを示した.
- 著者
- 但馬 康宏 富田 悦次 若月 光夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.97, no.356, pp.111-118, 1997-10-31
- 参考文献数
- 4
- 被引用文献数
- 1
単純決定性言語の多項式時間MAT学習に関する新たな結果を示す。一般に等価性質問は、仮説文法の入力に対して学習対象の言語との等価性を出力とし、さらに非等価の場合には、その根拠となる反例も出力となる。ここで、反例が正の反例の場合、さらに学習対象における導出構造を出力する質問を構造反例付き等価性質問と新たに定義する。このとき、任意の単純決定性言語は、単純決定性言語の族を用いて、所属性質問および構造反例付き等価性質問から多項式時間で厳密学習可能であることを示す。この学習アルゴリズムの基本的な考え方はAngluin (1987) によるアルゴリズムの拡張である。