ダウンロード数: 26
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-031-32726-1_21.pdf | 413.7 kB | Adobe PDF | 見る/開く |
タイトル: | Optimal General Factor Problem and Jump System Intersection |
著者: | Kobayashi, Yusuke https://orcid.org/0000-0001-9478-7307 (unconfirmed) |
著者名の別形: | 小林, 佑輔 |
発行日: | 2023 |
出版者: | Springer Nature |
誌名: | Integer Programming and Combinatorial Optimization - 24th International Conference(IPCO) |
開始ページ: | 291 |
終了ページ: | 305 |
抄録: | In the optimal general factor problem, given a graph G=(V, E) and a set B(v)⊆ℤ of integers for each v∈V, we seek for an edge subset F of maximum cardinality subject to dF(v)∈B(v) for v∈V, where dF(v) denotes the number of edges in F incident to v. A recent crucial work by Dudycz and Paluch shows that this problem can be solved in polynomial time if each B(v) has no gap of length more than one. While their algorithm is very simple, its correctness proof is quite complicated. In this paper, we formulate the optimal general factor problem as the jump system intersection, and reveal when the algorithm by Dudycz and Paluch can be applied to this abstract form of the problem. By using this abstraction, we give another correctness proof of the algorithm, which is simpler than the original one. We also extend our result to the valuated case. |
記述: | 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023 Part of the Lecture Notes in Computer Science book series (LNCS, volume 13904) |
著作権等: | This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-031-32726-1_21 The full-text file will be made open to the public on 22 May 2024 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/284971 |
DOI(出版社版): | 10.1007/978-3-031-32726-1_21 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。