WEKO3
アイテム
距離独立集合問題および誘導マッチング問題に対する近似アルゴリズム
https://doi.org/10.18997/00007214
https://doi.org/10.18997/00007214fc091980-64d2-46db-80e5-90a65e24c256
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
jou_k_339.pdf (1.2 MB)
|
|
| アイテムタイプ | 学位論文 = Thesis or Dissertation(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-06-13 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||
| 資源タイプ | doctoral thesis | |||||||||
| タイトル | ||||||||||
| タイトル | Approximation Algorithms for Distance Independent Set and Induced Matching Problems | |||||||||
| 言語 | en | |||||||||
| タイトル | ||||||||||
| タイトル | 距離独立集合問題および誘導マッチング問題に対する近似アルゴリズム | |||||||||
| 言語 | ja | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 著者 |
柳, 植竜
× 柳, 植竜
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | This thesis deals with the following two problems, the Maximum Distance-d Independent Set problem （MaxDdIS for short） and the Maximum Induced Matching problem （MaxIM for short）, where d ≥ 3. We design some approximation algorithms to solve MaxDdIS and MaxIM. （1） We first study MaxDdIS. Our main results for MaxDdIS are as follows: （i） It is NP-hard to approximate MaxD3IS on 3-regular graphs within 1.00105 unless P=NP. （ii） For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard, and show the inapproximability of MaxDdIS on r-regular graphs. （iii） We design polynomial-time O（rd-1）-approximation and O（rd-2/d）- approximation algorithms for MaxDdIS on r-regular graphs. （iv） We sharpen the above O（rd-2/d）-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. （v） Furthermore, we design a polynomial-time 1.875-approximation algorithm for MaxD3IS on cubic graphs. （vi） Finally, we consider planar graphs and obtain that MaxDdIS admits a polynomial-time approximation scheme （PTAS） for planar graphs. （2） We then investigate MaxIM on r-regular graphs. For subclasses of r-regular graphs, several better approximation algorithms are known. The previously known best approximation ratios for MaxIM on C5-free r-regular graphs and C3, C5 -free r-regular graphs are （3r/4 - 1/8 + 3/16r - 8） and （0.7084r + 0.425）, respectively. We design a （2r/3 + 1/3） -approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one for C5-free r-regular graphs when r ≥ 6, and for {C3, C5 }-free r-regular graphs when r ≥ 3. | |||||||||
| 目次 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 1 Introduction||2 Preliminaries||3 Maximum Distance-d Independent Set problem||4 Maximum Induced Matching Problem||5 Conclusion | |||||||||
| 備考 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 九州工業大学博士学位論文 学位記番号：情工博甲第339号 学位授与年月日：平成31年3月25日 | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Approximation | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Distance | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Independent Set | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Induced Matching | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Regular Graphs | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Planar Graphs | |||||||||
| アドバイザー | ||||||||||
| 宮野, 英次 | ||||||||||
| 学位授与番号 | ||||||||||
| 学位授与番号 | 甲第339号 | |||||||||
| 学位名 | ||||||||||
| 学位名 | 博士（情報工学） | |||||||||
| 学位授与年月日 | ||||||||||
| 学位授与年月日 | 2019-03-25 | |||||||||
| 学位授与機関 | ||||||||||
| 学位授与機関識別子Scheme | kakenhi | |||||||||
| 学位授与機関識別子 | 17104 | |||||||||
| 学位授与機関名 | 九州工業大学 | |||||||||
| 学位授与年度 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 平成30年度 | |||||||||
| 出版タイプ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| アクセス権 | ||||||||||
| アクセス権 | open access | |||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||
| ID登録 | ||||||||||
| ID登録 | 10.18997/00007214 | |||||||||
| ID登録タイプ | JaLC | |||||||||
