ダウンロード数: 0
このアイテムのファイル:
このアイテムは一定期間後に公開されます。
公開日については,アイテム画面の「著作権等」でご確認ください。
公開日については,アイテム画面の「著作権等」でご確認ください。
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Bousquet, Nicolas | en |
dc.contributor.author | Hommelsheim, Felix | en |
dc.contributor.author | Kobayashi, Yusuke | en |
dc.contributor.author | Mühlenthaler, Moritz | en |
dc.contributor.author | Suzuki, Akira | en |
dc.contributor.alternative | 小林, 佑輔 | ja |
dc.date.accessioned | 2023-11-21T00:55:47Z | - |
dc.date.available | 2023-11-21T00:55:47Z | - |
dc.date.issued | 2023-11-10 | - |
dc.identifier.uri | http://hdl.handle.net/2433/286140 | - |
dc.description.abstract | We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to 𝘒₃, ₃ -minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non-maximum independent parity sets. | en |
dc.language.iso | eng | - |
dc.publisher | Elsevier BV | en |
dc.rights | © 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ | en |
dc.rights | The full-text file will be made open to the public on 10 November 2025 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. | en |
dc.rights | This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください | en |
dc.subject | Feedback vertex set | en |
dc.subject | Combinatorial reconfiguration | en |
dc.subject | Polynomial-time algorithm | en |
dc.subject | Planar graph | en |
dc.subject | Matroid parity | en |
dc.title | Feedback vertex set reconfiguration in planar graphs | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Theoretical Computer Science | en |
dc.identifier.volume | 979 | - |
dc.relation.doi | 10.1016/j.tcs.2023.114188 | - |
dc.textversion | author | - |
dc.identifier.artnum | 114188 | - |
dcterms.accessRights | embargoed access | - |
datacite.date.available | 2025-11-10 | - |
datacite.awardNumber | 20K11692 | - |
datacite.awardNumber | 20H05795 | - |
datacite.awardNumber | 22H05001 | - |
datacite.awardNumber | 18H04091 | - |
datacite.awardNumber | 20K11666 | - |
datacite.awardNumber | 20H05794 | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11692/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05795/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22H05001/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H04091/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11666/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05794/ | - |
dc.identifier.pissn | 0304-3975 | - |
dc.identifier.eissn | 1879-2294 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.awardTitle | 組合せ最適化における多面体手法の高度化 | ja |
jpcoar.awardTitle | 数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ | ja |
jpcoar.awardTitle | グラフアルゴリズム基盤と最適化:理論研究と高速アルゴリズム開発 | ja |
jpcoar.awardTitle | 理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究 | ja |
jpcoar.awardTitle | 組合せ遷移による常時稼働型システムの構成最適化 | ja |
jpcoar.awardTitle | 工学アプローチによる組合せ遷移の展開:配電切替を足がかりとして汎用ソルバーへ | ja |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。