非サイクル有向グラフの極大パス被覆を求めるアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
一般の (サイクルをもつ) 有向グラフに対して、最小の構成成分 (パス) によるそのグラフの被覆を求める問題すなわち、'極大パス被覆問題'はNP完全であることが知られている。n頂点のサイクルのない有向グラフ (以下'非サイクル有向グラフ'と呼ぶ) G=(V, E) に対する、極大パス被覆問題については、O(n^<5/2>) 時間のものが知られている。また最大入次数、最大出次数のどちらか一方または、両方が高々2のグラフに関しては、深さ優先探索によるO(n) 時間のアルゴリズムが知られている。本論文では、一般の非サイクル有向グラフに対して、(2) のアルゴリズムより単純なアルゴリズムを提案する。
- 社団法人電子情報通信学会の論文
- 1997-03-06
著者
-
守谷 哲夫
国士舘大学理工学部
-
片岳 格
国士舘大学理工学部
-
守谷 哲夫
国士舘大学工学部電気電子工学科
-
片岳 格
国士舘大 理工
-
片岳 格
国士舘大学工学研究科応用システム工学専攻
-
片岳 格
国士舘大学大学院工学研究科
-
守谷 哲夫
国士舘大学
関連論文
- Some families of codes under the pure codes and the bifix codes (Algebras, Languages, Algorithms in Algebraic Systems and Computations)
- Literal shuffle on $\omega$-languages(Semigroups, Formal Languages and Computer Systems)
- 診断結果を論理式で表現した故障診断システム(研究速報)
- d-primitive words and D(1)-concatenated words (Algorithmic and Computational Theory in Algebra and Languages)
- 論理式を用いた故障診断システムについて
- 無向グラフの隣接次数表と最小サイクル表 : 位数制限グラフの同型性
- 隣接次数表による無向グラフが同型であるための十分条件
- 符号のSyntactic congruence
- 非サイクル有向グラフの極大パス被覆を求めるアルゴリズム
- Membership of words in Codes
- Syntactic Congruences of some Codes (Algebraic Systems, Formal Languages and Computations)
- Closure property of Some Codes under Composition (Languages, Algebra and Computer Systems)
- 符号の合成について
- 上昇型プッシュダウン木オートマトンと文脈自由木文法
- ある無限列が表現する実数の集合
- Morphism preserving some kinds of languages (Algebras, Languages, Algorithms and Computations)
- Closure properties of $\omega$-languages under morphism and inverse morphism