ダウンロード数: 150
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-030-45771-6_22.pdf | 352.96 kB | Adobe PDF | 見る/開く |
タイトル: | Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles |
著者: | Kobayashi, Yusuke https://orcid.org/0000-0001-9478-7307 (unconfirmed) |
著者名の別形: | 小林, 佑輔 |
キーワード: | Triangle-free 2-matchings b-factors Extended formulation Polynomial-time algorithm |
発行日: | 2020 |
出版者: | Springer Nature |
誌名: | Integer Programming and Combinatorial Optimization |
巻: | 12125 |
開始ページ: | 280 |
終了ページ: | 293 |
抄録: | The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give a first polynomial-time algorithm for the weighted T -free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T -free 2-matching problem. |
記述: | 21st International Conference, IPCO 2020, London, UK, June 8-10, 2020. |
著作権等: | This is a post-peer-review, pre-copyedit version of an article published in Integer Programming and Combinatorial Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-45771-6_22. The full-text file will be made open to the public on 14 April 2021 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/252767 |
DOI(出版社版): | 10.1007/978-3-030-45771-6_22 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。