単位円グラフ上の最大独立集合問題の近似解法
スポンサーリンク
概要
- 論文の詳細を見る
単位円グラフは, 2次元平面上の単位円の交差グラフである。本稿では, 単位円グラフ上の最大独立集合問題の解法を提案する。頂点数nの単位円グラフが, 幅kの横長の板の上に定義されている場合, 最大独立集合を見つけるO(n4[2k/φ1)時間の解法を提案する。また一般の単位円グラフに付いては, 最大独立集合問題の(1-1/r)-近似解法で, 時間計算量がO(rn4[2(r-1)/′/3])となるものを提案する。
- 一般社団法人情報処理学会の論文
- 1999-03-15
著者
関連論文
- オークションの設計理論とOR(2)(数理計画の理論と実装)
- 数理計画の理論と実装 : オークションの設計理論とOR(1)(ネットワークシステムのセキュリティ評価と危機管理)
- DS-1-3 閉ジャクソンネットワークに対するMCMC法(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 完璧にサンプリングしよう! : 第三話 終わりある未来
- 完璧にサンプリングしよう! : 第二話 天と地の狭間で
- Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
- 完璧にサンプリングしよう! : 第一話 遥かなる過去から
- スポーツスケジューリング : 未解決問題を中心に
- 閉ジャクソンネットワークに対するパーフェクトサンプリング法
- 三角格子点上の単位円グラフに対する多重彩色
- 閉ジャクソンネットワークに対するパーフェクトサンプリング法
- 三角格子点上の単位円グラフに対する多重彩色
- 離散化Dirichlet分布に従うパーフェクトサンプリング
- $m×n$分割表の近似数え上げスキームの提案 (計算機科学基礎理論の新展開)
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- ディジタルハーフトーニング : ネットワークフローアルゴリズムによる最適化
- Dirichlet分布のrapidly mixing approximate sampler
- Dirichlet 分布の rapidly mixing approximate sampler
- 偽金貨を探そう(高校生のためのOR)
- Farkasの補題と双対定理の初等的証明
- 1993年Jリーグの再スケジューリング
- スポーツのスケジューリング (スポーツの戦術とマネジメント)
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- MAX DICUT問題の近似解法 (計算理論とアルゴリズムの新展開)
- Arrowの一般可能性定理の証明の解説
- 半正定値計画を描いた最大カット問題.878近似解法
- チャネル割当問題の解法
- チャンネル割当問題の解法
- 相補スラック定理から入ってみたら
- 2×n型双行列ゲームのNash均衡点を求める図解法
- 単位円グラフ上の最大独立集合問題の近似解法