フローネットワークにおける最小k-Spanner問題のNP-完全性について
スポンサーリンク
概要
- 論文の詳細を見る
フローネットワークにおける最小kーSpanner問題とはフローネットワークNにおいて, すべての点対間容量が1/k倍以上となる辺数最小なspanner(全域部分グラフ)Sを求める問題である.すなわちNの任意の2点u, vの点対間容量をc_N(u, v), Sの任意の2点u, vの点対間容量をc_S(u, v)とするとc_N(u, v)≤k・c_S(u, v)となる辺数最小のSを求める問題である.本報告では3-SAT問題をk-Spanner問題に多項式変換を行うことでNP-困難性を証明する.
- 2000-01-20
著者
-
田村 裕
新潟工科大学工学部情報電子工学科
-
仙石 正和
新潟大学工学部情報工学科
-
渡辺 郁
大阪電気通信大学情報工学部
-
田村 裕
新潟工科大学工学部
-
仙石 正和
新潟大学工学部
-
田村 裕
新潟工科大学
関連論文
- 並列分散システムにおけるデータ配信アルゴリズム (VLSI設計技術)
- 並列分散システムにおけるデータ配信アルゴリズム (回路とシステム)
- 企業における先端的な技術開発と「ものづくりの実際」を学習するプログラム「企業Week」
- 無線通信におけるネットワークコーディングを用いた情報転送の効率化について
- マルチホップ無線ネットワークのアクセスポイントへ接続する端末数について
- AS-1-1 ネットワークコーディングに関連したグラフの辺彩色問題(AS-1. グラフ理論と組合せアルゴリズム,シンポジウムセッション)
- 格子状マルチホップ無線ネットワークにおける経路ETXの解析
- マルチホップ無線ネットワークにおける経路品質の解析(グラフ,ペトリネット,ニューラルネット及び一般)
- マルチホップ無線網におけるホップ数と中継負荷を考慮した中継局配置手法に関する考察(セキュリティ,信頼性,モバイル,一般)
- (110)高大接続の観点から見た専門高校卒業生の4年生大学工学部への受け入れ : 新潟大学における10年間の実践に関する報告(セッション32 高大連携I)
- ネットワークコーディングとグラフの辺彩色問題について(グラフ,ペトリネット,ニューラルネット及び一般)
- ある種の並列分散システムにおけるブロードキャストスケジューリング(グラフ,ペトリ,ニューラルネット及び一般)
- 広域並列分散システムのブロードキャストスケジューリングについて(グラフとネットワーク)
- 最新グラフネットワーク理論とその応用
- 異動クラスタシステムのブロードキャストスケジューリングに関する一考察
- [招待論文]グラフ理論,確率幾何学の移動通信への応用
- マルチホップ無線通信におけるチャネル割当に関する一考察
- アドホックネットワークにおける隣接端末情報の必要性
- チャネル数を考慮した無線アドホックネットワークの情報配信問題
- 無向フローネットワークのminimax実現問題のある一般化について
- 拡張された辺彩色問題の点彩色問題への変換について
- 企業における先端的な技術開発と「ものづくりの実際」を学習するプログラム「企業 Week」
- 企業連携による実践的工学キャリア教育プログラムの開発
- 拡張された辺彩色問題の点彩色問題への変換について(研究速報)
- フローネットワークにおける最小k-Spanner問題のNP-完全性について
- いくつかの要求を満足する無向フローネットワークの実現について
- フローネットワークのロケーション問題の一考察
- 実践的工学教育における学外技術者による支援状況
- 企業連携による実践的工学キャリア教育プログラムの開発の最終年度の取組成果
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- CAS2010-4 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- B-5-185 多値QAM変調方式を使用したFWAシステムに適用するMLSE干渉補償装置の演算量削減に関する一検討(B-5.無線通信システムB(ワイヤレスアクセス),通信1)
- GPS, 歩数計及び方位計を用いた歩行者移動経路追跡法(GPS論文小特集)
- B-7-22 端末間直接通信と端末の移動の関係についての考察
- 端末の移動が端末間通信に及ぼす影響について
- マルチホップ無線ネットワークにおける経路品質の解析(グラフ,ペトリネット,ニューラルネット及び一般)
- 2.地震からの復興に向けて : 新潟県中越沖地震被災地から(自然災害からの復興の取組みと課題)
- 企業や社会との連携で進める実践的工学教育プログラムの実施状況
- UMTSにおける移動ネットワーク通信とQoS制御(無線通信交換)
- UMTSにおけるネットワークモビリティの提供(ブロードバンド無線アクセス技術、IPをサポートする無線アクセス技術、一般)
- UMTSにおけるネットワークモビリテイの提供(ブロードバンド無線アクセス技術,IPをサポートする無線アクセス技術,一般)
- ネットワークコーディングとグラフの辺彩色問題について(グラフ,ペトリネット,ニューラルネット及び一般)
- 無線アドホックネットワークの技術動向
- 無線アドホックネットワークの技術動向
- B-7-36 PHSを用いた地域・情報通信ネットワークにおける情報配信時間
- SA-6-6 セルラ移動通信と割当問題
- 有向グラフのカット被覆問題とその応用
- マルチホップ型移動通信網の中継局配置問題
- ネットワークにおけるある種の配送問題について
- フローネットワークの出口配置問題
- 遺伝的アルゴリズムを用いたセルラ移動通信系におけるダイナミックチャネル割当に関する一考察
- ギガビットネットワークを用いた遠隔ストレージ間編集用映像配信実験
- ギガビットネットワークを用いた遠隔ストレージ間編集用映像配信実験
- ギガビットネットワークを用いた遠隔ストレージ間編集用映像配信実験
- MIGヘッド記録磁界の有限要素解析 : 画像情報記録
- 道路網における移動体の流れと移動通信トラヒック
- 道路網における移動体の流れと移動通信トラヒック
- 道路網モデルを用いた移動通信系の通信トラヒック特性の解析
- 同期距離のマークグラフ上への実現について
- 駐車場の効率的な除雪に関する一考察
- 時間限界値をもつ最小コスト木問題の一考察
- 回路とシステム、コンピュータならびに通信に関する国際会議
- コンテンツ処理を含む通信コーディネーションの一提案(コンテンツ,P2P,バーチャル・リアリティとマルチモーダル・インタフェースおよび一般)
- コンテンツ処理を含む通信コディネーションの一提案
- コンテンツ処理を含む通信コーディネーションの一提案
- ある種の並列分散システムにおけるブロードキャストスケジューリング(グラフ,ペトリ,ニューラルネット及び一般)
- マルチホップ無線通信におけるチャネル割当に関する一考察
- 無向フローネットワークのminimax実現に関する問題のNP完全性について
- 無向フローネットワークのminimax実現に関する問題のNP完全性について
- グラフ理論, 確率幾何学とモバイルコミュニケーション
- グラフ理論, 確率幾何学とモバイルコミュニケーション
- グラフ理論, 確率幾何学とモバイルコミュニケーション
- ユニバーサルアドホックネットワークにおける情報配信アルゴリズムのグラフ理論的考察
- 彩色ネットワークにおけるリソース数の最小化について
- アドホックネットワークにおける情報配信問題へのグラフ理論的アプローチ
- アドホックネットワークにおける情報配信問題へのグラフ理論的アプローチ
- ユニバーサル・アドホックネットワークの検討 : 木状ネットワークに対する情報配信アルゴリズム
- グラフ・ネットワーク理論の倉庫の片隅に積まれている問題
- 端子容量行列とは限らない行列からの無向フローネットワークの実現について
- 無向フローネットワークのminimax実現問題の一般化について
- 5. 周波数有効利用技術におけるグラフネットワーク理論の適用 (情報通信の将来の基礎に向けて)
- グラフ・ネットワーク理論とその応用の今後
- いくつかの要求を満足する無向フローネットワークの実現について
- 端子容量行列を実現するフローネットワークの構造
- 端子容量行列を実現するネットワークのもつ構造について
- オンデマンド型ルーティングにおける安定ルートの構築
- ニューラルネットワークを用いた寸法の異なるVLSIモジュールの配置手法
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マークグラフ上へ実現可能な同期距離の性質について
- マークグラフ上へ実現可能な同期距離の性質について
- クラスタを用いるアドホックネットワークにおける効率的なフラッディング方式
- B-7-60 クラスタリングを利用した効率的なパケットフラッディング方式
- 無向フローネットワークにおける総合被覆問題について
- フローネットワークにおける拡張された被覆問題について
- AS-1-3 木状のグラフへのいくつかの辺彩色と色数について(AS-1.組み合わせ最適化の最新動向,シンポジウムセッション)