ダウンロード数: 56
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
20m1364370.pdf | 1.41 MB | Adobe PDF | 見る/開く |
タイトル: | Shortest Reconfiguration of Perfect Matchings via Alternating Cycles |
著者: | Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke https://orcid.org/0000-0001-9478-7307 (unconfirmed) Okamoto, Yoshio |
著者名の別形: | 小林, 佑輔 |
キーワード: | graph algorithms matching combinatorial reconfiguration combinatorial shortest paths 05C85 52B05 |
発行日: | 2022 |
出版者: | Society for Industrial & Applied Mathematics (SIAM) |
誌名: | SIAM Journal on Discrete Mathematics |
巻: | 36 |
号: | 2 |
開始ページ: | 1102 |
終了ページ: | 1123 |
抄録: | Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar. |
著作権等: | © 2022, Society for Industrial and Applied Mathematics |
URI: | http://hdl.handle.net/2433/279146 |
DOI(出版社版): | 10.1137/20m1364370 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。