無向グラフにおけるk-辺分割問題の一般化について
スポンサーリンク
概要
- 論文の詳細を見る
G=(V,E)を無向グラフとする.指定辺付k-辺分割問題は,Gのk本の辺e_1,…,e_kおよび辺数|E|のk個の正整数への分割m_1+…+m_k=|E|が与えられたとき,次の(1)(2)を満たすEの分割E_1∪…∪E_kを求める問題である.(1)e_1∈E_i,|E_i|=m_i(i=1,…,k,(2)各E_iに誘導される部分グラフが連結になる.Gがk-辺連結ならば,(1)(2)を満たす分割が必ず存在することが知られているが,分割を具体的に多項式時間で求めるアルゴリズムはk≤3の場合にのみ知られており,k>4については未解決である.本報告では,より一般化したラベル指定k-辺分割問題を導入する.すなわち,Gの各点に{1,…,k}から選んだラベルを自由に付したグラフ,および辺数の分割m_1+…+m_k=|E|に対し,次の(i)-(ii)の条件を満たす辺集合Eの分割E_1,…,E_kを求める問題である.(i)|E_i|=m_i(i=1,…,k),(ii)各E_iの誘導するグラフの各連結成分はラベルiのついた点を少なくとも1個含む.本報告では,k=2,3の場合について,この問題の分割が存在する十分条件を与え,この条件の下で分割を見つけるO(|E|)時間(k=2の場合)および,O(|E|+|V|^2)時間(k=3の場合)の多項式時間アルゴリズムを構築する.
- 社団法人電子情報通信学会の論文
- 1995-09-22
著者
関連論文
- タンク繰りにおける経路探索法
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
- 無向グラフにおける節点領域間の辺連結度を増大させる問題について
- 動的交通流配分のネットワーク・モデル
- スケジューリングの理論
- 無向ネットワーク内の全ての最小カットを表すカクタス表現の構成について(グラフ理論(1))
- 2つの資源節点集合をもつ3点連結グラフを均等分割するロバストアルゴリズム
- 部分定義論理関数のホーン拡張について
- オプションプライシングと凸計画問題の関係について(金融工学(3))
- 給油施設操業スケジューリング
- 1-D-8 紙管製造工程における1次元カッティングストック問題(離散アルゴリズム(3))
- ネットワークの辺連結度増加問題を解くアルゴリズムの計算機実験(グラフ理論(2))
- アルゴリズム研究会(研究会千夜一夜)
- 離散構造を紐解くグラフ連結度アルゴリズム(文献賞受賞招待講演)
- 1-F-2 時間依存距離付きネットワークにおける2地点間の最短路アルゴリズム(動的計画)
- 領海毎に連結度要求の異なるNA辺連結度増大問題について
- 劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
- 辺連結度増加関数の計算法(ネットワーク(1))
- タンク繰りスケジューリングに対する二段階アルゴリズム(組合せ最適化)
- 最小費用流アルゴリズムを用いたタンク繰りスケジューリング構成法(スケジューリング)
- 3以下の局所点連結度要求を持つグラフのコスト付き供給点配置問題
- 3以下の局所点連結度要求を持つグラフの供給点配置問題
- A Ranged Laminar Family in Graphs and Its Application (Mathematical Optimization Theory and its Algorithm)
- An $O(mn+n^2log n)$ Time Cactus Construction Algorithm (Mathematical Optimization Theory and its Algorithm)
- 無向グラフにおける局所点連結度増大問題について
- TD-1-10 グラフの最小カットを計算しよう
- On the Minimum Augmentation of an l-Connected Graph to a k-Connected Graph
- Augmenting a (k-1)-Vertex-Connected Multigraph to an l-Edge-Connected and k-Vertex-Connected Multigraph
- (l-1)-点連結グラフをk-辺連結かつl-点連結に増大させる問題
- グラフをk-辺連結かつ3-点連結に最適増大させる問題
- Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
- Augmenting edge-connectivity and vertex-connectivity simultaneously
- 辺連結度,点連結度を同時に最適増大させる問題
- 機械式立体駐車場入出庫スケジューリング
- 機械式立体駐車場出庫スケジューリング
- 無向ネットワークの最小カットを求める実用的高速アルゴリズム(グラフ・ネットワーク)
- A Tight Upper Bound on the Number of Small Cuts in Undirected Networks
- 内視鏡手術 直腸癌に対する腹腔鏡下低位前方切除術
- Vehicle Scheduling on a Tree to Minimize Maximum Lateness(スケジューリング(2))
- リリースタイムとハンドリングタイムを考慮した木状経路における搬送スケジューリング(スケジューリング)
- 結腸右半切除術 (特集 はじめての手術手技--どのように教えるか)
- 最近のアルゴリズムから : OR若手から一言(OR : 21世紀に向けて)
- 正理論関数の部分データに基づく正決定木の構成について(組み合わせ最適化(3))
- メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
- オイラー有向グラフにおける2本の辺素なパスの存在判定
- 最小カット問題の簡潔かつ構成的な証明
- 手術手技 尿管下腹神経筋膜を温存する側方リンパ節郭清術
- PS-125-3 大腸sm癌境界病変における手術成績(PS-125 ポスターセッション(125)大腸:手術-3,第111回日本外科学会定期学術集会)
- 最適化アルゴリズムの最近の動き
- PS-145-5 骨盤外科の将来的展望 : 下部消化管外科の意義(PS-145 ポスターセッション(145)その他-1,第111回日本外科学会定期学術集会)
- VF-018-4 進行大腸癌に対する"日本式"腹腔鏡下大腸切除術(VF-018 大腸:鏡視下手術-3,第111回日本外科学会定期学術集会)
- VF-003-2 尿路変更における尿管回腸吻合の工夫 : 腸間膜貫通前壁吻合(VF-003 ビデオフォーラム(3)大腸:手術,第111回日本外科学会定期学術集会)
- 無向グラフにおけるκ-辺分割問題の一般化について(組合せ最適化(3))
- 無向グラフにおけるk-辺分割問題の一般化について
- 腹腔鏡下大腸癌根治術におけるこだわりのデバイス : 超音波凝固切開装置,波形鉗子,ラパロ用筋鉤 (特集 こだわりのデバイス)
- 腹腔鏡下腹壁瘢痕ヘルニア修復術(腹壁貫通固定法) (特集 ヘルニア手術を究める)
- 手術手技 尿路変更における尿管回腸吻合の工夫 : 腸間膜貫通前壁吻合
- 腹腔鏡下低位前方切除術 (特集 達人こだわりの手術テクニック) -- (胃腸食道領域)
- 腹腔鏡下低位前方切除術における術中トラブルへの対処 (特集 内視鏡手術におけるトラブルシューティング)
- 大腸がん腹腔鏡手術の現状と未来 (特集 外科治療 : さらなる進化に向けて)
- PS-086-2 大腸癌術後肝転移切除症例における低酸素関連因子発現の検討 : ブリングル法の影響について(PS-086 大腸 転移,ポスターセッション,第112回日本外科学会定期学術集会)
- VD-006-3 下部直腸癌に対する腹腔鏡下直腸切除術の確実な神経温存手技と成績(VD-006 ビデオセッション(6)大腸 低侵襲・機能温存,第112回日本外科学会定期学術集会)
- PS-088-6 腹腔鏡下結腸切除術におけるドレーン留置の必要性の検討(PS-088 大腸 鏡視下-1,ポスターセッション,第112回日本外科学会定期学術集会)
- PS-014-3 結腸癌術後補助化学療法におけるlow risk StageIIIaの提案(PS-014 大腸 化学療法-1,ポスターセッション,第112回日本外科学会定期学術集会)
- PS-013-1 腹腔鏡下右側結腸癌根治術における郭清リンパ節個数およびリンパ節転移の検討(PS-013 大腸 リンパ節郭清,ポスターセッション,第112回日本外科学会定期学術集会)
- SF-005-1 当院における直腸癌側方郭清の短期・中期成績(SF-005 サージカルフォーラム(5)大腸 リンパ節郭清-1,第112回日本外科学会定期学術集会)
- PS-134-6 腹腔鏡下低位前方切除および腹腔鏡下ISRの左結腸動脈温存についての検討(PS-134 大腸 鏡視下,ポスターセッション,第112回日本外科学会定期学術集会)