| Item type |
学術雑誌論文 / Journal Article.(1) |
| 公開日 |
2020-06-25 |
| 書誌情報 |
en : IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
巻 E96D,
号 11,
p. 2327-2332,
発行日 2013
|
| タイトル |
|
|
タイトル |
On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
3-regular graph |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
bipartite permutation graph |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
feedback vertex set |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
grid intersection graph |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
nonseparating independent set |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| アクセス権 |
|
|
アクセス権 |
open access |
|
アクセス権URI |
http://purl.org/coar/access_right/c_abf2 |
| 著者 |
髙岡, 旭
田湯, 智
上野, 修一
|
| 室蘭工業大学研究者データベースへのリンク |
|
|
表示名 |
髙岡 旭（TAKAOKA Asahi） |
|
URL |
http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html |
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n(2) log(6) n) time for n-vertex graphs with maximum degree at most three. |
|
言語 |
en |
| 出版者 |
|
|
出版者 |
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG |
|
言語 |
en |
| 出版者版へのリンク |
|
|
表示名 |
10.1587/transinf.E96.D.2327 |
|
URL |
https://doi.org/10.1587/transinf.E96.D.2327 |
| DOI |
|
|
関連タイプ |
isIdenticalTo |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
10.1587/transinf.E96.D.2327 |
| 日本十進分類法 |
|
|
主題Scheme |
NDC |
|
主題 |
548 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1745-1361 |
| 権利 |
|
|
言語 |
en |
|
権利情報 |
Copyright © 2013 IEICE |
| 参考URL |
|
|
|
識別子タイプ |
URI |
|
|
関連識別子 |
https://search.ieice.org/index.html |
|
|
言語 |
en |
|
|
関連名称 |
IEICE Transactions Online TOP |
| 著者版フラグ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| フォーマット |
|
|
内容記述タイプ |
Other |
|
内容記述 |
application/pdf |
IEICETIS_96_11_2327_2332 (362.1 kB)
