マトロイド被覆問題に対する発見的手法(セッション1)
スポンサーリンク
概要
- 論文の詳細を見る
マトロイド被覆問題とは,グラフの樹相度を求める問題を一般化した問題である.マトロイド被覆問題は多項式時間で解けるものの,その時間計算量は決して低くない.近年,川野等は既に知られていたグラフの樹相度(edge arboricity)に対する線形時間で動作する2倍近似アルゴリズムを,マトロイド被覆問題に対する発見的アルゴリズムに拡張した.本研究ではこの川野等が提案したアルゴリズムを,cographicマトロイドとstrict gammoidと呼ばれる2つのマトロイド上の被覆問題に対して実装し,実験的評価を行った.
- 一般社団法人情報処理学会の論文
- 2006-05-18
著者
-
大舘 陽太
群馬大学工学研究科
-
山崎 浩一
群馬大学工学研究科
-
山崎 浩一
玉川大学 工学部
-
山崎 浩一
玉川大学工学部メディアネットワーク学科
-
大舘 陽太
群馬大学工学部情報工学科
-
青木 一正
群馬大学工学研究科
-
青木 一正
群馬大学 工学部 情報工学科
-
大舘 陽太
群馬大学 工学部 情報工学科
-
山崎 浩一
群馬大学 工学部 情報工学科
-
青木 一正
群馬大学工学部情報工学科
-
山崎 浩一
Department Of Computer Science Gunma University
関連論文
- 原発巣の自然退縮中に脳転移が出現した肺大細胞癌の1例
- 正則グラフのデカルト冪に対するカービング幅 (理論計算機科学の深化と応用)
- 偶グリッドのカービング幅
- Bipartite Permutation Graphのランダム生成と列挙
- Approximating the path-distance-width for asteroidal triple-free graphs (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- W8-5 肺肉腫様癌の細胞所見(肺多形がんの細胞像,細胞学・基礎と臨床の架け橋,第49回日本臨床細胞学会総会(春期大会))
- 7.EBUS-GS併用TBBで診断に至らずCT透視下TBBを施行した肺末梢小型病変の検討(第30回日本呼吸器内視鏡学会北海道支部会)
- OR11-2 EBUS-GS併用TBBで診断に至らずCT透視下TBBを施行した肺末梢小型病変の検討(仮想気管支鏡・極細経気管支鏡,一般口演11,第31回日本呼吸器内視鏡学会学術集会)
- 重症気道熱傷後に気管・気管支狭窄を合併しバルーン拡張術が有効であった1例
- OR11-5 気管支鏡挿入支援システムは肺末梢小型病変に対する経気管支生検の診断率を上昇させ,検査時間を短縮する(仮想気管支鏡・極細経気管支鏡,一般口演11,第31回日本呼吸器内視鏡学会学術集会)
- Y4-3 気管支鏡挿入支援システム(VTR・診断,要望演題4,第31回日本呼吸器内視鏡学会学術集会)
- S1-4 Virtual Bronchoscopic Navigationシステムによる肺末梢病変の診断(内視鏡による新しい診断方法(末梢部病変),シンポジウム1,第31回日本呼吸器内視鏡学会学術集会)
- WS4-2 EGFR遺伝子変異を有する進行非小細胞肺癌患者を対象としたgefitinib治療prospective試験統合解析(分子標的治療2(臨床),第49回日本肺癌学会総会号)
- 7. 肺末梢良性病変におけるガイドシース併用気管支腔内超音波断層法を用いた気管支鏡検査の有用性の検討(第29回日本呼吸器内視鏡学会北海道支部会)
- Expected Length of Longest Common Subsequences of Two Biased Random Strings and Its Application (Algorithm Engineering as a New Paradigm)
- 7.EGFR遺伝子変異を有する進行非小細胞肺癌に対するゲフィチニブの臨床試験への取り組み(第33回日本肺癌学会北海道支部会,支部活動)
- 木幅の上界を求めるMCSアルゴリズムについて
- スクィズド状態における位相の量子雑音解析
- OR11-3 極細径気管支鏡を用いたCT透視下経気管支生検にて診断し,動体追跡放射線照射で治療した末梢小型肺癌の検討(仮想気管支鏡・極細経気管支鏡,一般口演11,第31回日本呼吸器内視鏡学会学術集会)
- WS1-3 再発小細胞肺癌に対するアムルビシンとノギテカンの無作為化第II相試験(小細胞肺癌の治療,第49回日本肺癌学会総会号)
- グラフクラスと部分グラフ同型性
- 12-108 全人教育に根ざした導入教育 : 玉川大学の低学年次導入教育 : 機械システム学科の実施例を中心にして((25)リメディアル教育(補習教育)・導入教育-I)
- A-6-8 Yuen-Kim暗号鍵配送方式に対する光増幅器を用いた盗聴法(A-6.情報理論,一般セッション)
- A-6-7 Yuen-Kim暗号鍵配送方式に関する一考察 : 受信者の誤り率に制限を加えたときの鍵生成速度(A-6. 情報理論, 基礎・境界)
- TB-3-3 量子情報科学が可能にする通信技術
- 古典雑音に基づく秘密鍵配送の一実現法
- TA-2-6 量子暗号鍵配送系のための誤り訂正符号
- SA-5-5 量子暗号の基礎
- A-186 2値位相変調スクイズド状態信号に対する準最適量子受信機(A-7. 情報理論,一般講演)
- k-bounded hole familyに対するlongest induced path問題を解くアルゴリズムの改善(セッション3)
- M元PSKコヒーレント状態信号における信号の遷移確率を考盧した符号化変調方式(研究速報)
- M元コヒーレント状態信号における信号の状態を考慮した信号配置による通信路符号化
- M元コヒーレント状態信号におけるトレリス符号化変調方式のビット誤り率
- 3次元格子グラフのパス幅
- 完全$k$分木のpath distance widthについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 外平面グラフに対するsecurity number
- d-claw freeグラフの重み付き最大独立集合問題に対するタブーサーチ法の提案
- 完全2分木に対するPath Distance Width の下界(計算機科学の理論とその応用)
- マトロイド被覆問題に対する発見的手法(セッション1)
- d-claw freeグラフの重み付き最大独立集合問題に対する近似アルゴリズムの実験的評価
- バンド幅縮小問題に対する遺伝的アルゴリズム
- An approximation algorithm for matroid covering (Theoretical Computer Science and its Applications)
- レベル構造に基づいたバンド幅縮小アルゴリズムが苦手とするグラフクラス
- レベル構造に基づいたバンド幅縮小アルゴリズムが苦手とするグラフクラス
- 完全k分木に対するvertex isoperimetric numberの下界
- 完全κ分木に対する vertex isoperimetric number の下界
- 区間2部グラフと単位格子交差グラフの関係について
- 区間2部グラフと単位格子交差グラフの関係について
- グラフのデカルト積における木幅の下界
- グラフのデカルト積における木幅の下界
- 新しい量子状態変換機構の一提案
- 量子暗号方式の秘匿性の増強について
- 葉の個数を指定した順序木の列挙
- 衛星ステレオ画像データの可逆符号化方式に関する検討
- 衛星ステレオ画像データの可逆符号化方式に関する検討
- 光電変換過程に伴う量子状態変換の量子通信への応用
- 量子通信のための光受信システム条件
- スクイズィング角の現象論的意味付け
- 量子暗号鍵配送におけるスクィズド状態の有効性
- SA-4-3 対話型秘密鍵系列の一致のための完全符号
- SA-4-1 既存完全符号の秘密鍵系列の一致への適用法
- 秘密鍵系列の一致のための完全符号
- PA-3-2 量子暗号鍵配送系の設計理論
- 秘密鍵系列の一致プロトコル"Cascade"に関する一考察-その3-
- 系列の一致プロトコル"Cascade"に関する一考察
- 系列の一致プロトコル"Cascade"に関する一考察
- 系列の一致プロトコル"Cascade"に関する一考察
- 光マイクロフォンシステム : レーザの自己注入現象を用いた変位測定
- Branch-length とtree-length(計算機科学の理論とその応用)
- J.ホロムコヴィッチ(著), 和田幸一, 増澤利光, 元木光雄(訳), "計算困難問題に対するアルゴリズム理論 組合せ最適化・ランダマイゼーション 近似・ヒューリスティクス", シュプリンガー・フェアラーク東京(2005-12), A5判, 定価(本体7,500円+税)
- 独立な雑音に基づく鍵配送方式における光増幅器の影響
- M元直交コヒーレント状態信号の量子最適受信機の実現化問題(量子情報理論とその応用)
- M元光直交信号の最適受信に関する一考察
- 光M元直交信号の準最適受信機に関する一考察
- 全域木混雑度に対するメタヒューリスティックアルゴリズムの評価 (コンピュテーション)
- 光マイクロフォンシステム : レーザの自己注入現象を用いた変位測定
- 光マイクロフォンシステム : レーザの自己注入現象を用いた変位測定
- マトロイド被覆問題に対する近似アルゴリズム
- バンド幅問題に対する遺伝的アルゴリズムの交叉方法の提案 (計算機科学基礎理論の新展開)
- 線形刻み幅の双対定理について (計算機科学とアルゴリズムの数理的基礎とその応用)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- ハイパーリングの厚さについて
- properとunitのgrid graphに関する研究
- On greedy algorithms for maximum weighted independent set problem (Models of Computation and Algorithms)
- 重み付きグラフの独立点集合に関する考察
- 全域木混雑度に対するメタヒューリスティックアルゴリズムの評価
- 単位格子交差グラフについての考察
- Pathwidthがk, strong pathwidthがkのグラフに対するページナンバー
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 単位円交差グラフの線形構造を持つ部分クラスについて (アルゴリズムと計算理論の新展開)
- 施設配置ゲームにおける仁・シャープレイ値の計算について (Theoretical Foundations of Computing)
- Stripグラフについて
- 3次元直方体のintersection graphに対する独立点集合問題の近似困難について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
- 『電子情報通信レクチャーシリーズ B-6 オートマトン・言語と計算理論』, 岩間一雄(著), 電子情報通信学会編, コロナ社, 2003-11, B5判, 定価(本体3,000円+税)
- バンド幅問題に対するvolume respecting embedding法の実験的評価 (計算機科学基礎理論の新展開)
- 矩形によるインターセクショングラフに関する近似アルゴリズムについて (新しいパラダイムとしてのアルゴリズム工学)
- Path Distance Widthの近似について
- 多項式個の極小セパレータを持つグラフクラスについて (理論計算機科学の新展開)
- Stripグラフについて