Approximating Bounded Degree Deletion via Matroid Matching

• Item type: SIG Technical Reports(1)
• 公開日: 2017-05-05
• タイトル: Approximating Bounded Degree Deletion via Matroid Matching
• タイトル / 言語: en
• タイトル: Approximating Bounded Degree Deletion via Matroid Matching
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Computer Science & Engineering, Toyohashi University of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science & Engineering, Toyohashi University of Technology
• 著者名: Toshihiro, Fujimoto
• 著者名(英): Toshihiro, Fujimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The Bounded Degree Deletion problem with degree bound b : V → Z+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V, E) such that, when it is removed from G, the degree of any remaining vertex v is no larger than b (v). It will be shown that b-BDD can be approximated within max {2,b / 2 ＋ 1}, improving the previous best bound for 2 ≤ b ≤ 5, where b is the maximum degree bound, i.e., b = max {b (v)
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Bounded Degree Deletion problem with degree bound b : V → Z+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V, E) such that, when it is removed from G, the degree of any remaining vertex v is no larger than b (v). It will be shown that b-BDD can be approximated within max {2,b / 2 ＋ 1}, improving the previous best bound for 2 ≤ b ≤ 5, where b is the maximum degree bound, i.e., b = max {b (v)
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-163, 号 9, p. 1-7, 発行日 2017-05-05
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会