ある制限されたチャイニーズ・ポストマン問題の計算量
スポンサーリンク
概要
- 論文の詳細を見る
混合グラフのもとでのチャイニーズ・ポストマン問題(CPP)はNP完全であることが示されている. すべての辺の長さが等しい混合グラフ, 平面混合グラフ, 最大次数を3に制限した混合グラフのもとでさえNP完全である. 一方, グラフを全有向, または全無向に制限したCPPは多項式時間アルゴリズムを持つ. 本論文では, 各辺の通行回数をたかだか2回に制限したCPP (2-CPP)がNP完全であり, ちょうど1回に制限したCPP(1-CPP)はPに属することを示した. また, CPP に関連する2つの興味ある関数の計算量も示した: (i)2-CPPにおいて, 配達路の数を計算する関数は#P完全である, (ii)CPPにおいて, コスト k 以下で配達するためには, 同一辺を少なくとも何回通行しなければならないかを計算する関数は多項式時間階層のクラスΔ^P_2に属する.
- 一般社団法人情報処理学会の論文
- 1996-11-15
著者
関連論文
- 固定費付き輸送問題のための遺伝的アルゴリズムの提案と数値実験
- 暗号通信を用いたIP通信拡散手法
- 数値的三次元マッチング問題を利用した公開鍵暗号系の設計の設計
- P完全な2人完全情報ゲーム問題に対応する数え上げ問題はPに属する
- ナップザック問題が効率的に解けるための自明でない十分条件
- 部分グラフ彩色問題の計算量
- 道発見ゲーム問題の計算量
- ある制限されたチャイニーズ・ポストマン問題の計算量
- ある制限されたチャイニーズ・ポストマン問題の計算量(計算モデルと計算の複雑さに関する研究)
- ある制限されたチャイニーズ・ポストマン問題の計算量
- 2人ゲームにおける必勝手を数えあげる多項式時間アルゴリズム
- 容量なし施設配置問題のための遺伝的アルゴリズムの提案
- L-003 パケットフィルタリング機能を搭載したNICによるDoS攻撃対策(ネットワーク・セキュリティ,一般論文)
- 暗号通信を用いたIP通信拡散手法
- 暗号通信を用いたIP通信拡散手法
- 暗号通信を用いたIP通信拡散手法
- 不定方程式を用いた公開鍵暗号系の設計
- アドホックネットワークのためのチェックポイントプロトコルとその評価(会場B)
- アドホックネットワークのためのチェックポイントプロトコルとその評価(セッション4-A:アドホックネットワーク(2))
- チェックポイントプロトコル実行中のトポロジ変化を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(アドホックネートワーク(2))
- チェックポイントプロトコル実行中のトポロジ変化を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(アドホックネートワーク(2))
- アドホックネットワークのためのチェックポイントプロトコル(分散システム)
- アドホックネットワークのためのチェックポイントプロトコル(分散システム)
- 移動コンピュータの移動を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(セッション2: 分散システム・プロトコル)
- 移動コンピュータの移動を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(セッション2: 分散システム・プロトコル)
- アドホックネットワークのためのチェックポイントプロトコル(セッション1: プロトコル)
- [電子情報通信学会フェロー受賞記念講演]大学卒業後の40年を振り返って
- アドホックネットワークのためのチェックポイントプロトコルとその評価(セッション4-A:アドホックネットワーク(2))
- 複数の異なるチェックポイントの同時実行に対応したアドホックネットワークのためのチェックポイントプロトコル
- Generalizations of operator Shannon inequality based on Tsallis and Renyi relative entropies (Operator monotone functions and related topics)
- Extensions of relative operator entropies and operator $\alpha$-divergence (Operator monotone functions and related topics)