Triangle-free graphの独立集合問題に対する貪欲アルゴリズムの解析

• Item type: SIG Technical Reports(1)
• 公開日: 2008-01-23
• タイトル: Triangle-free graphの独立集合問題に対する貪欲アルゴリズムの解析
• タイトル / 言語: en
• タイトル: An Analysis of the Greedy Algorithm for Finding an Independent Set in a Triangle-free Graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者名: 小浦, 一平; 小野, 孝男; 平田, 富夫
• 著者名(英): Ippei, KOURA; Takao, ONO; Tomio, HIRATA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 独立集合問題の入力として頂点数nと平均次数dのグラフが与えられたとき，少なくともn/(d+1)のサイズの近似解を得る貪欲アルゴリズムがある．この値はTuran boundとして知られている．この貪欲アルゴリズムを線形計画法と組み合わせると(d+1)/2の近似率が得られる．本論文では，入力をtriangle-free graphに限定した独立集合問題において，貪欲アルゴリズムによってサイズが少なくとも2n/(d+4)の近似解が得られることを示す．更に，貪欲アルゴリズムと線形計画法を組み合わせると(d+4)/4の近似率が得られることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper treats the independent set problem. The greedy algorithm is well-known method for finding independent sets. The algorithm obtains an independent set of size at least n/(d+1), where n is the number of vertices and d is average degree. This value is known as “Turan bound”. Based on this result, Hochbaum showed that the greedy algoritm combined with LP attains performance ratio (d+1)/2. In this paper, restricting the input to triangle-free graphs, we show that the greedy algorithm obtains an independent set of size at least 2n/(d+4). We also prove that LP-based algorithm has the performance ratio (d+4)/4.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 6(2008-AL-116), p. 9-14, 発行日 2008-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会