3以下の局所点連結度要求を持つグラフのコスト付き供給点配置問題

スポンサーリンク

概要

• 論文の詳細を見る

• G=(V,E)が節点集合V,辺集合Eをもつ単純無向グラフであるとする.各節点v∈Vには,要求量と呼ばれる非負整数d(v)と費用と呼ばれる非負実数c(v)が与えられている.局所点連結度要求をもつグラフの供給点配置問題は,各節点v∈V-Sについて,節点集合Sとの間にv以外で節点を互いに共有しないようなパスがd(v)本以上存在するような費用和最小の節点集合Sを見つける問題である.これまでに,要求量が4以上の節点があるならば,全ての節点のコストが一定の場合でも,問題がNP困難であることが知られている.本稿では,各節点の要求量が3以下である場合について,問題を解く多項式時間アルゴリズムを提案する.

• 社団法人電子情報通信学会の論文
• 2003-07-25

著者

• 石井 利昌

  豊橋技術科学大学 工学部

• 永持 仁

  豊橋技術科学大学工学部情報工学科

• 永持 仁

  京都大学情報学研究科

• 藤田 等士

  豊橋技術科学大学情報工学系

• 石井 利昌

  豊橋技科大 工

関連論文

• 一次元連続ビンパッキング問題に対する厳密解法 (21世紀の数理計画 : アルゴリズムとモデリング)
• Approximating the generalized capacitated tree-routing problem (21世紀の数理計画--アルゴリズムとモデリング--RIMS研究集会報告集)
• 劣モジュラシステム分割問題に対するアルゴリズム
• タンク繰りにおける経路探索法
• タンク繰りにおける経路探索法(スケジューリング)
• 3つの資源節点集合を持つ4点連結グラフを均等分割する問題について(グラフ・ネットワーク(2))
• 2-D-19 最長路問題に対する次数2以下の点の除去処理とその分枝限定法での利用(離散最適化)
• 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
• 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
• 矩形パッキング問題に対する厳密解法
• 無向グラフにおける節点領域間の辺連結度を増大させる問題について
• 2-C-6 最長路問題に対する2連結成分分解にもとづく分枝限定法による厳密解法(グラフ・ネットワーク(1))
• 2つの資源節点集合をもつ3点連結グラフを均等分割するロバストアルゴリズム
• MAX-2-SATに対する分枝限定法
• オプションプライシングと凸計画問題の関係について(金融工学(3))
• グラフの最小5-カット, 6-カットを求めるアルゴリズム
• ディジタルハーフトーニング : ネットワークフローアルゴリズムによる最適化
• Digital Halftoning : Formulation as a Combinatorial Optimization Problem and Approximation Algorithms Based on Network Flow (Algorithm Engineering as a New Paradigm)
• グラフの極大成分を用いた生物ネットワークの解析(遺伝子発現・ネットワーク)
• 根付き三角化平面的グラフの列挙
• ビーコン配置問題と対偶問題に対する効率的近似アルゴリズム
• Classification by Ordering Data Samples (Acceleration and Visualization of Computation for Enumeration Problems)
• DS-1-5 An Efficient Algorithm for Large-scale Beacon Placement Problem
• 最小費用枝架設問題に対する近似解法
• Worst Case Analysis for a Pickup and Delivery Problem with Single Transfer (Numerical Optimization methods, theory and applications)
• P2Pシステムのための深さ最小木の構築について
• P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
• P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
• P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
• 容量付木状経路問題に対する近似解法
• 無向グラフにおける集合連結問題
• 反復構成特徴に基づいた分類器の実データへの拡張
• P2Pシステムのための深さ最小木の構築について (メディア工学)
• 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
• 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
• 辺連結度制約と次数制約をもつネットワーク設計問題
• 領海毎に連結度要求の異なるNA辺連結度増大問題について
• Construction of Visual Classifier by Edge Crossing Minimization (The evolution of optimization models and algorithms)
• A polynomial time approximation scheme for the minimum maximal matching problem in planar graphs (New Developments of Theory of Computation and Algorithms)
• 平面グラフにおける最小極大マッチング問題に対する多項式時間近似スキーム
• A Scheme for Generating Rooted Graphs with Reflectional Block Structures (The evolution of optimization models and algorithms)
• 最小コストκ分割を全て求めるアルゴリズム
• 光バースト交換網における専用波長を用いた全域木形成による衝突回避法
• 初等的フローゲームの凸性について(計算量理論とアルゴリズム論文小特集)
• タンク繰りスケジューリングに対する二段階アルゴリズム(組合せ最適化)
• 最小費用流アルゴリズムを用いたタンク繰りスケジューリング構成法(スケジューリング)
• 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
• 辺連結度,点連結度を同時に最適増大させる問題
• 内視鏡手術 直腸癌に対する腹腔鏡下低位前方切除術
• パス構造グラフにおける納期違反コスト最小化選択的配達スケジューリング(機械要素,潤滑,工作,生産管理など)
• 食品の袋詰め最適化問題に対する動的計画法(機械要素,潤滑,工作,生産管理など)
• パス型ネットワークにおける複数ビークルスケジューリング問題の2倍近似アルゴリズム
• Vehicle Scheduling on a Tree to Minimize Maximum Lateness(スケジューリング(2))
• 平成5年度春季研究発表会 ルポ
• リリースタイムとハンドリングタイムを考慮した木状経路における搬送スケジューリング(スケジューリング)
• 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム
• 結腸右半切除術 (特集 はじめての手術手技--どのように教えるか)
• グラフの比例分割について
• 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
• 最小カット問題の簡潔かつ構成的な証明
• 手術手技 尿管下腹神経筋膜を温存する側方リンパ節郭清術
• Greedy Splitting : A Unified Approach for Approximating Some Partition Problems (Mathematical Optimization Theory and its Algorithm)
• A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)
• 最小3-カットを使った最小k-カットの近似
• 長さに上限をもつパスによる有向グラフの被覆に対するアルゴリズム
• 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-辺分割問題の一般化について
• 辺支配集合問題の2倍近似アルゴリズム
• 局所辺連結度を保存するオイラーグラフ節点分離
• Approximation Algorithm for Optimization Problems Related to the Edge Dominating Set (最適化数理の手法と実際 RIMS研究集会報告集)
• 重み付き次数制約を持つネットワーク設計問題
• A 2-packing of three 3-based graphs in a 3-connected graph
• 最小費用3点連結部分グラフを求める問題に対する近似アルゴリズム
• パス頻度の上下限制約を満たす木状化合物の二段階列挙法
• 1-D-1 Algorithms for Covering Digraphs by Length-Bounded Walks
• 腹腔鏡下大腸癌根治術におけるこだわりのデバイス : 超音波凝固切開装置,波形鉗子,ラパロ用筋鉤 (特集 こだわりのデバイス)
• 腹腔鏡下腹壁瘢痕ヘルニア修復術(腹壁貫通固定法) (特集 ヘルニア手術を究める)
• 手術手技 尿路変更における尿管回腸吻合の工夫 : 腸間膜貫通前壁吻合
• 腹腔鏡下低位前方切除術 (特集 達人こだわりの手術テクニック) -- (胃腸食道領域)
• 腹腔鏡下低位前方切除術における術中トラブルへの対処 (特集 内視鏡手術におけるトラブルシューティング)
• 大腸がん腹腔鏡手術の現状と未来 (特集 外科治療 : さらなる進化に向けて)
• 2-E-4 忌避型施設配置ゲームにおける戦略耐性メカニズムの特徴付け(ゲーム理論(2))
• PS-086-2 大腸癌術後肝転移切除症例における低酸素関連因子発現の検討 : ブリングル法の影響について(PS-086 大腸 転移,ポスターセッション,第112回日本外科学会定期学術集会)
• 平面無向グラフで2番目に短い経路を求めるアルゴリズム

もっと見る 閉じる

スポンサーリンク