ある種の非サイクル的有向グラフに対する極大パス被覆問題の並列計算量
スポンサーリンク
概要
- 論文の詳細を見る
非サイクル的有向グラフ(DAG)を頂点の重複しないパスにより被覆する問題を扱う,この"パス被覆"においてパスの本数が最小のときそのパス被覆は"極大"と言われる.我々は,DAGの極大パス被覆を与える問題^<(3)〜(7),(9),(13),(17)>の並列計算量を考え,その結果入次数または出次数のうちのどちらか一方がたかだか2のときこの問題がクラスNCに属することを示した.更にこの結果により,片方の頂点集合の次数がたかだか2であるような2部グラフの極大マッチング問題もクラスNCに属することが示される.
- 社団法人電子情報通信学会の論文
- 1993-12-25
著者
関連論文
- 直方体分割の24次格子グラフ表現とその応用 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 24分格子グラフによる直方体分割の描画
- 24分格子グラフによる直方体分割の描画
- 年長園児における加法逆減法問題の理解度 : 自己を含む場合と他者のみの場合の比較
- 4L-4 組み込みソフト向けHichart開発環境における動作仕様検査(要求定義とプログラミング言語・設計・実装,学生セッション,ソフトウェア科学・工学)
- 研究情報推移グラフによる情報の個人管理・共有手法(コンテンツ技術,データ工学論文)
- 学術論文関係情報のグラフ描画問題に基づく視覚化手法(教育工学)
- Syntactic Characterization of Two-Dimensional Grid Graphs by a Context-Sensitive Graph Grammar(New Trends in Theory of Computation and Algorithm)
- グラフ文法による図と表の処理の定式化
- 3B-7 Octgridに基づく表編集アルゴリズム(アルゴリズムとその応用,一般セッション,ソフトウェア科学・工学)
- 2B-2 最急降下モデルによる日本全域尾根線つき3次元地形図の作成(数理モデル化と問題解決,一般セッション,ソフトウェア科学・工学)
- D-12-32 Octgridに基づく効率的な3D地形図生成法(D-12.パターン認識・メディア理解A(パターンメディアの認識・理解・生成),一般セッション)
- 表の格子グラフモデルと編集アルゴリズム
- 多層型矩形分割に対する16分格子グラフ表現 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- D-3-3 組み込みソフトウェア向けHichart処理系の開発(D-3. ソフトウェアサイエンス,一般セッション)
- D-1-4 Octgridに対する属性グラフ文法による矩形数え上げ(D-1. コンピュテーション,一般セッション)
- A-6-13 24-ary Grid Graph Representation for the Rectangular Solid Dissections
- K-019 3D偏光立体視システムを利用した地理情報教材(K分野:教育工学・福祉工学・マルチメディア応用)
- A-003 8分格子モデルを用いた地形的特徴の認識システム(A分野:モデル・アルゴリズム・プログラミング)
- D-12-12 H7CODEに基づくVRML地形図エディタの開発(D-12.パターン認識・メディア理解,一般講演)
- D-1-3 Octgridに対するパーザの開発(D-1.コンピュテーション,一般講演)
- D-1-2 スライス構造の表に対するグラフ文法(D-1.コンピュテーション,一般講演)
- 3D立体表示による地理・地学教育支援教材の応用可能性(教育におけるセキュリティ/一般)
- 6H-1 初期官報バックナンバー閲覧システムの開発(情報システムのインタフェース,一般セッション,コンピュータと人間社会)
- 表編集のアルゴリズム (計算機科学基礎理論の新展開)
- J-047 多重解像度3D地形図の8分グラフ表現(J分野:グラフィクス・画像)
- バス・スヌープ方式のディスクシステムへの適用と性能評価
- 地形の特徴抽出モデルと3次元地形図への応用(セッション6)
- 属性グラフ文法によるビジネス文書の定式化(セッション3)
- グラフ文法によるビジネス文書の定式化の試み
- 木構造図式の描画問題
- 境界付きNLCグラフ文法の性質(計算および計算量理論とその周辺)
- ある種の非サイクル的有向グラフに対する極大パス被覆問題の並列計算量
- ある種の非サイクル的有向グラフの極大パス被覆を与える線形時間アルゴリズム
- 有向グラフに対する極大パスカバー問題の計算量(計算量理論とその周辺)
- Complexity of Path Covering Problems in Acyclic Alternate Graphs II(Algorithms : Mathematical Foundations and Applications)
- COMPLEXITY OF PATH COVERING PROBLEMS IN ACYCLIC ALTERNATE GRAPHS(Mathematical Foundations of Computer Science and Their Applications)
- VRMLによる3D地形図を利用した地理・地学のためのWBTコンテンツ(教育実践システムと学習評価/一般)
- オントロジーに基づく数学教育支援システムの提案(教育実践システムと学習評価/一般)
- D-3-9 Hichart エディタにおける属性評価による開発支援機能
- D-3-4 ソフトウェア仕様書の XML によるデータベース化
- 表インターフェースのための属性付きグラフとアルゴリズム
- D-3-1 属性edNCEグラフ文法に基づくHichartエディタ
- プログラム図式を用いたプログラム開発教育環境
- オントロジーに基づく数学教育支援システムの提案 (教育実践システムと学習評価)
- 米国算数教科書紹介(7)
- 米国算数教科書紹介(VI)
- 米国算数教科書紹介(V)
- 米国算数教科書紹介(IV)
- 米国算数教科書紹介(III)
- 米国算数教科書紹介(II)
- 米国算数教科書紹介(I)
- 強連結オートマトンとその商オートマトンの自己同型群(計算量理論の諸相 : その基礎的研究)
- 強連結オートマトンとその商オートマトンの自己同形群
- 商オートマトンの自己同型群について
- ニ部グラフの最長初等道と最長初等閉路について (形式言語理論とオートマトン理論)
- D-12-3 Octgridに基づく3D地形図の自動生成(D-12.パターン認識・メディア理解,一般セッション)
- 最急上昇法による尾根抽出 (計算機科学とアルゴリズムの数理的基礎とその応用)
- Hichart プログラム図式の生成手法
- Hichartプログラム図式の生成手法
- B2 年長園児における加法逆減法問題の理解度 : 自己を含む場合と他者のみの場合の比較(B 問題解決(1)(問題解決・指導法等),論文発表の部)
- 8次格子モデルによる表の行/列操作 (アルゴリズムと計算理論の新展開)
- 8次格子グラフによる2次元画像の解像度低減化
- 8次格子グラフによる2次元画像の解像度低減化