パスグラフから区間グラフへの最小辺付加による変換の NP 完全性
スポンサーリンク
概要
- 論文の詳細を見る
一つの木の上の道の集合が与えられたとき,道に対応して頂点をもち,二つの道が交わるとき対応する頂点が辺で結ばれているようなグラフをパスグラフと呼ぶ.直線上の有限個の区間の集合Aが与えられたとき,Aに属する区間を頂点とし二つの区間が交わるとき間に辺を持つようなグラフを区間グラフと呼ぶ.本研究では,パスグラフにK本以下の本数の辺を付加して区間グラフに変換することができるか否かを判定する問題がNP完全であることを証明する.
- 社団法人電子情報通信学会の論文
- 1994-09-25
著者
-
荒木 俊郎
茨城大学工学部情報工学科
-
山口 一章
大阪大学基礎工学部情報工学科
-
荒木 俊郎
大阪大学基礎工学部情報工学科
-
柏原 敏伸
大阪大学基礎工学部情報工学科
-
柏原 敏伸
大阪大学大学院
-
柏原 敏伸
大阪大学基礎工学部
-
荒木 俊郎
茨城大学
関連論文
- 状態遷移図に基づくビジュアルWebブラウザプログラミングの提案(研究速報,サイバーワールド論文)
- 低開発コストの分散計算方式の構築
- stグラフの道独立頂点集合の性質
- 2つのグラフの共通st順序付けのNP完全性
- 第一階述語論理のサブクラスに対する近似的モデル検査アルゴリズム
- PASCALシンボリック・デバッガの作成
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- 1-有界無競合ペトリネットにおける二つのトランジションの同時発火可能性を判定するYenのアルゴリズムの改良
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- ペトリネットの部分クラスにおける同時発火可能性
- 局所変数を含むアサーションに対するモデルチェッキングのためのチェッカ生成(アサーションベース検証,システム設計及び一般)
- 局所変数を含むアサーションに対するモデルチェッキングのためのチェッカ生成(システム設計及び一般)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 定数幅量子ブランチングプログラムの計算能力 (計算理論とアルゴリズムの新展開)
- 1回読み定数幅制約下での量子ブランチングプログラムと確率ブランチングプログラムの計算能力の比較
- クロネッカー式関数決定グラフの最適展開規則選択問題の計算複雑度(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 二分モーメントグラフによる除算表現の大きさの指数下界 (アルゴリズムと計算の理論)
- 二分モーメントグラフによる除算表現の大きさの指数下界
- 妨害者のいる場合の最短経路問題
- 妨害の下での最短経路問題の複雑さ : 通過後の妨害を許さない場合
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- 妨害の下での最短経路問題
- パスグラフから区間グラフへの最小辺付加による変換の NP 完全性
- 交互シャフルについて
- 木上二重コンベックスグラフと二部サークルグラフの等価性
- 端子間に配線を通過させない順列配線のビア数最小化アルゴリズム
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- パスグラフから区間グラフへの最小辺付加による変換のNP完全性
- ある種のグラフにおける最大クリーク重みの折点数について
- ユーザインタフェース作成支援システムの設計と試作について
- 同期付シャフル表現の記述能力
- 同期付線型シャフル文法と対向ヘッド・シャフル・スタック・オ-トマトン
- シャフル文法に関する決定問題
- 同期付シャフル文法
- DNA演算シミュレータの構築
- 複数のグラフの同時平面描写について
- ミニコンによるある連想記憶システムの作成について
- 言語Cのライブラリ形式によるコンカレント機能の実現
- 分散型システム記述用言語Concurrent Cの設計とその処理系の実現
- 低開発コストの分散計算方式の構築
- 低開発コストの分散計算方式の構築
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(ハードウェア,フォーマルアプローチ論文)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- 平面グラフの最大重み窓問題
- 外窓上の頂点および辺の重みの和を最大にするような,2連結平面グラフの描写アルゴリズム
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- コンパラビリティグラフから得られるst有向グラフのセパレータ
- An Algorithm for Generating Maximum Weight Independent Sets in a Circle Graph
- パラメトリックグラフにおける最大クリ-ク重みの折れ点数
- あるグラフの極大頂点集合を表現するダイアグラム
- 階層的グラフの平面性判定アルゴリズム
- 2層配線における3端子ネットの分割
- 部品の端子間に配線を通過させない一層配線問題について
- 部品の反転を許さない一層平面配線問題について
- 対話型修正編集機能を持つPASCAL構文解析システム
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定(検証・理論, 組込技術とネットワークに関するワークショップ)
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定(検証・理論, 組込技術とネットワークに関するワークショップ)
- 同期付正規シャフル文法と同期付生成システムの記述能力
- 正規シャフル文法に関する一考察(技術談話室)
- オブジェクト指向設計記述言語ODDJの設計とその記述環境の開発(開発支援(1))
- ペトリネットに関する幾つかの決定不能問題
- 線型シャフル文法とシャフル文法で生成される言語の諸性質
- シャフル文法
- PASCAL内部手続きの分離翻訳
- VLIWプロセッサにおける演算命令発行スロット数の最適化
- VLIWプロセッサにおける演算命令発行スロット数の最適化
- VLIWプロセッサ自動生成における演算器構成最適化の一手法
- VLIWプロセッサ自動生成における演算器構成最適化の一手法
- ある書式記述言語の設計と処理ルーチン
- シャフル・スタック・オ-トマン
- シャフルを付け加えた正規表現に関する決定問題
- シャフルを付け加えた正規表現(技術談話室)
- システム記述用言語Cのポータブルコンパイラの作成
- フロ-表現とイベント表現の記述能力
- フロ-表現の等価問題の決定不能性