節点と節点部分集合間の2および3点連結化問題
スポンサーリンク
概要
- 論文の詳細を見る
グラフにその節点部分集合(領域)族を与えた領域グラフと、従来からある点連結度の概念を拡張した節点と領域間の点連結度であるNA(node-to-area)点連結度という概念が提案されている。本稿では、k=1, 2, 3に対し、与えられた領域グラフのk-NA点連結性を判定するための必要十分条件と、これらの条件を用いたk-NA点連結性判定の多項式時間アルゴリズムを示す。また、k-NA点連結でない領域グラフが与えられたとき、領域に最少数の節点を付加することによってk-NA点連結にするk-NA点連結化問題についても、k≤2に対しては線形時間アルゴリズムを、k=3に対しては、本問題がNP完全であることを示す。
- 社団法人電子情報通信学会の論文
- 1998-03-24
著者
-
上原 秀幸
豊橋技術科学大学情報工学系
-
伊藤 大雄
京都大学大学院情報学研究科通信情報システム専攻
-
伊藤 大雄
豊橋技術科学大学
-
横山 光雄
豊橋技術科学大学情報工学系
-
上原 秀幸
豊橋技術科学大学未来ビークルリサーチセンター
-
伊藤 資泰
豊橋技術科学大学 情報工学系
-
横山 光雄
豊橋技術科学大学情報工学専攻科
-
Ito H
Tokyo Inst. Of Technol. Yokohama‐shi Jpn
-
上原 秀幸
豊橋技術科学大学大学院電気・電子情報工学系
-
上原 秀幸
豊橋技術科学大学
関連論文
- 非同期型無線センサネットワークにおける擬似同期MACプロトコルの特性評価(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- エスパアンテナを用いた時空間MACプロトコルのスループット特性評価(有線/無線シームレスネットワーク,ハンドオーバ,リレー,分散MIMO,モバイル・アドホックネットワーク,一般)
- 3素子エスパアンテナの試作と性能評価実験(衛星,移動通信におけるアンテナ・伝搬技術,一般)
- 両端末に3素子エスパアンテナを用いた秘密鍵共有システムの基礎実験(有線/無線シームレスネットワーク,ネットワーク制御,無線通信一般)
- ゲートとソースにスタブを装荷したFET発振回路の基本設計(マイクロ波信号発生と計測技術/一般)
- Deafnessと隠れ端末問題に対処する指向性MACプロトコルの適応キャリアセンシング (ネットワークシステム)
- センサネットワークにおけるデータ属性を考慮したデータ伝送制御方式の提案(モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- マルチホップ無線ネットワークにおける優先領域に基づく中継制御法(無線アドホックネットワーク技術論文特集)
- フェージング通信路で同期検波を実現する位相同期回路(ブロードバンド無線アクセス技術, 無線通信一般, 信号処理)
- B-21-19 マルチホップ通信環境におけるNAV Blocking問題とDeafness問題について(B-21.アドホックネットワーク,一般セッション)
- エスパアンテナを用いたアドホック無線のための時空間MACプロトコル(有線/無線シームレスネットワーク,ネットワーク制御,無線通信一般)
- Cycle-and-Add特性に基づいたDS-CDMA用干渉除去方式のマルチパスフェージング通信路での特性評価(次世代ネットワーク,電力線通信,無線通信方式,一般)
- 最大相関値検出に基づくDS-CDMA用シングルユーザ型干渉除去方式のレイリーフェージング通信路における特性(誤り訂正,MAC,無線通信一般)
- DS-CDMAにおけるCycle-and-Add特性を利用した干渉除去方式(スペクトル拡散技術)
- A-21-9 センサネット適応ルーティングの消費電力特性と結合エントロピー(A-21.センサネットワーク,一般講演)
- B-5-73 DS/CDMAシステムにおける微分積分処理を用いた干渉除去方式(B-5.無線通信システムA(移動通信),一般講演)
- B-21-2 干渉除去とコードセンス機能を持つアドホックネットワーク用CDMA型MACプロトコル(B-21.アドホックネットワーク,一般講演)
- B-8-7 マルチレートDS-CDMAシステムにおける適応干渉除去方式(B-8.通信方式,一般講演)
- Gold符号におけるCycle-and-Add特性について(研究速報)
- A-21-25 観測データに基づき省電力化を図るセンサネットクラスタリングスキーム(A-21.センサネットワーク,一般講演)
- パイロット信号による位相変動を補償した定包絡線化BPSK変調方式(衛星通信システムと衛星搭載機器及び一般)
- センサネットワークにおけるcoverageとノードアクティビティについて(ネットワーク構成, センサネットワーク論文)
- A-21-8 観測値データに基づき協調制御するセンサネットワーク・クラスタリング(A-21.センサネットワーク,基礎・境界)
- B-5-88 DS/CDMAシステムのためのマルチパスフェージング通信路における適応干渉除去方式の性能改善(B-5.無線通信システムA(移動通信),通信1)
- B-3-7 カルマンフィルタによる位相雑音の予測(B-3.衛星通信,通信1)
- B-3-6 パイロット信号による位相雑音低減と定包絡線化(B-3.衛星通信,通信1)
- B-21-6 CDMAに基づくアドホックネットワーク用MACプロトコル(B-21.アドホックネットワーク, 通信2)
- B-6-63 DS-CDMA上りリンクにおける最小電力割当によるスケジューリングについて(B-6.ネットワークシステム, 通信2)
- B-5-2 Cycle-and-Add特性を利用したGold符号用DS-CDMA同期システムの性能評価(B-5. 無線通信システムA(移動通信), 通信1)
- B-5-1 Cycle-and-Add特性を利用した干渉除去方式の遠近問題への適用(B-5. 無線通信システムA(移動通信), 通信1)
- 車両間マルチホップ無線ネットワークにおける方向指定ルーチング(ITS通信技術, ITS技術論文)
- Cycle-and-Add特性を利用した干渉除去方式(ブロードバンド無線アクセス技術, IPをサポートする無線アクセス技術, 光無線システム, 無線通信一般, およびRCS/CS各研究会一般テーマ)
- IEEE 802.11 DCF MACを用いた無線アドホックネットワークの通信容量に関する一考察(ブロードバンド無線アクセス技術, IPをサポートする無線アクセス技術, 光無線システム, 無線通信一般, およびRCS/CS各研究会一般テーマ)
- Cycle-and-Add特性を利用したDS-CDMA用同期システムの性能評価(アダプティブアンテナ,MIMO及び無線信号処理技術,無線通信一般)
- 無線マルチホップ環境におけるRTS/CTS機構に起因するNAV Blocking問題の改善について(無線通信一般)
- マルチホップ無線ネットワークにおける方向指定ルーチングの特性評価(モバイルQos, ユビキタス, アドホックNW, 及び一般)
- B-5-179 フェージング通信路における位相情報を利用したDS/CDMA用干渉除去受信機の検討(B-5.無線通信システムA(移動通信))
- B-5-162 Cycle-and-Add特性を利用したDS-CDMA同期回路のフェージング通信路での同期検出確率(B-5.無線通信システムA(移動通信))
- B-5-151 速いレイリーフェージング通信路におけるDS/CDMA用干渉除去方式の性能改善(B-5.無線通信システムA(移動通信))
- B-5-180 アドホックネットワークのマルチホップ環境における IEEE 802.11 DCF の特性改善
- アドホックルーチングプロトコルにおけるノードの移動情報を利用したモビリティメトリックの検討(有線無線シームレス, モバイルネットワーキング, Mobile IP, 無線通信, ネットワーク制御, 一般)
- 無線アドホックネットワークにおける指向性MACを利用したルーティングプロトコルの基本検討(有線無線シームレス, モバイルネットワーキング, Mobile IP, 無線通信, ネットワーク制御, 一般)
- リンクとノードのコストを基にして指標切り替えを行うアドホックルーチングプロトコル(有線無線シームレス, モバイルネットワーキング, Mobile IP, 無線通信, ネットワーク制御, 一般)
- アドホックルーチングプロ斗コルにおけるノードの移動情報を利用したモビリティメトリックの検討(有線無線シームレス,モバイルネットワーキング,Mobile IP,無線通信,ネットワーク制御,一般)
- 無線アドホックネットワークにおける指向性MACを利用したルーティングプロトコルの基本検討(有線無線シームレス,モバイルネットワーキング,Mobile IP,無線通信,ネットワーク制御,一般)
- リンクとノードのコストを基にして指標切り替えを行うアドホックルーチングプロトコル(有線無線シームレス,モバイルネットワーキング,Mobile IP,無線通信,ネットワーク制御,一般)
- 非希望信号発生回路を用いたDS-CDMA用適応干渉除去方式のフェージング下における収束特性の向上について(有線無線シームレス, モバイルネットワーキング, Mobile IP, 無線通信, ネットワーク制御, 一般)
- 非希望信号発生回路を用いたDS-CDMA用適応干渉除去方式のフェージング下における収束特性の向上について(有線無線シームレス,モバイルネットワーキング,Mobile lP,無線通信,ネットワーク制御,一般)
- B-5-341 アドホックネットワークにおけるモビリティメトリックに関する検討
- メディア統合予約型CDMAパケット通信における隣接セル干渉を考慮したスケジューリング方式
- メディア統合CDMAパケット無線ネットワークにおけるMACプロトコル(次世代移動通信ネットワークとその応用)
- リンクの寿命とノードの負荷を考慮したアドホックルーチングプロトコルの特性評価(無線アドホックネットワーク技術論文特集)
- 端末のパケット中継機能を用いた安否確認ネットワークの検討(無線アドホックネットワーク技術論文特集)
- 搬送波位相情報を利用した DS/CDMA 用干渉キャンセラ
- 加群上の畳込み符号による可変レートMPSK符号化変調方式
- OCDMにおけるFIR型等化器を用いた自己相関サイドローブ抑圧法
- メディア統合CDMAパケツト無線ネットワークにおけるチャネル割当方式
- 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
- メディア統合CDMAパケット無線ネットワークにおけるチャネル割当方式
- B-10-126 遅延ロックループを用いたOCDM用同期回路
- B-5-205 マルチホップ無線ネットワークにおける優先領域に基づくルーチングプロトコルの検討
- B-5-204 通信可能時間を考慮したアドホックルーチングプロトコルの特性評価
- B-5-115 フーリエ変換/逆変換によるDS-CDMA用干渉キャンセラ
- B-5-114 微分・積分操作を利用したDS-CDMA用干渉除去方式
- B-3-30 衛星通信における位相情報を利用したDS-CDMA用干渉キャンセラ
- レイリーフェージング通信路に有効な環上の畳込み符号
- circulant制約を持った隣接色制約付き彩色問題の応用と解析 (計算理論とアルゴリズムの新展開)
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- B-5-149 ルーチングゾーンを用いた車々間通信プロトコル
- B-5-140 アドホックネットワークにおけるリンク間コストを考慮したルーチングプロトコル
- B-5-66 フェージング環境下における簡易受信方式の性能評価
- B-5-63 送信タイミング制御を用いたメディア統合予約型CDMAパケット通信方式
- B-5-7 フェージング環境における簡易干渉除去方式の性能評価
- B-5-6 フェージング通信路における位相情報を利用したDS-CDMA用干渉除去受信機特性
- SB-11-3 DS-CDMAシステムにおける簡易適応干渉除去方式
- B-5-169 メディア統合無線ネットワークにおける予約符号を用いたアクセス制御方式
- B-5-168 マルチホップ無線ネットワークにおける優先領域に基づくパケット中継制御法
- B-5-107 スペクトル拡散通信用簡易受信方式 : 簡易PN同期回路の並列接続による性能改善
- B-5-78 レイリーフェージング環境における位相情報を利用したDS-CDMA用干渉除去受信機特性
- 次数制限付最短路木に関する諸問題(グラフ・ネットワーク(2))
- 安否確認ネットワークにおける送信制御のパラメータの影響
- 音声・データ統合予約型パケット無線アクセス方式の検討
- 位相情報を利用したスペクトル拡散通信用干渉除去方式
- DS-CDMAシステムにおける適応干渉除去方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- DS-CDMAにおけるMMSE法を用いた干渉除去方式
- サウンダー信号を持つBPSK変調方式の定包絡線化と特性解析
- k-NA枝連結かつ2-NA点連結な最小領域配置問題(グラフ・ネットワーク(1))
- 一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮
- B-5-122 スペクトル拡散通信用簡易受信方式
- B-5-110 スペクトル拡散通信用簡易干渉除去受信方式
- B-5-109 DS-CDMAシステムにおける干渉除去方式
- B-5-108 DS-CDMA システムにおける非直線特性を利用した干渉除去方式
- B-5-26 サウンダー信号を持つBPSK変調方式の定包絡線化
- B-5-4 隣接位置情報を用いた安否確認ネットワークの構築
- 有向グラフ上の高枝連結節点部分集合生成アルゴリズム
- 次数制限のある最短路木作成アルゴリズム
- 舞台照明問題のNP完全性(計算幾何学・図解法)
- 正補混合表現によるグラフ探索時間の削減
- 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討