WEKO3
アイテム
An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs
http://hdl.handle.net/10228/00007440
http://hdl.handle.net/10228/00007440a9267ea7-6d66-49b1-b23c-dad411f2f039
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
transfun.E102.A.1142.pdf (1.9 MB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-11-19 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs | |||||||||||||
| 言語 | en | |||||||||||||
| その他のタイトル | ||||||||||||||
| その他のタイトル | An approximation algorithm for the maximum induced matching problem on C5-free regular graphs | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi× Lin, Guohui× Liu, Zhilong× 宮野, 英次
WEKO
6037
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $\left(\frac{3d}{4}-\frac{1}{8}+\frac{3}{16d-8}\right)$. In this paper, we design a $\left(\frac{2d}{3}+\frac{1}{3}\right)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6. | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E102-A, 号 9, p. 1142-1149, 発行日 2019-09-01 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | 電子情報通信学会 | |||||||||||||
| 言語 | ja | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1587/transfun.E102.A.1142 | |||||||||||||
| 日本十進分類法 | ||||||||||||||
| 主題Scheme | NDC | |||||||||||||
| 主題 | 548 | |||||||||||||
| NCID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA10826261 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0916-8516 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1745-1345 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2019 The Institute of Electronics, Information and Communication Engineers | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | induced matching problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | C5-free regular graph | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | approximation algorithm | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10347275 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 7935 | |||||||||||||
