ダウンロード数: 150
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-030-45771-6_22.pdf | 352.96 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Kobayashi, Yusuke | en |
dc.contributor.alternative | 小林, 佑輔 | ja |
dc.date.accessioned | 2020-07-17T06:32:11Z | - |
dc.date.available | 2020-07-17T06:32:11Z | - |
dc.date.issued | 2020 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2433/252767 | - |
dc.description | 21st International Conference, IPCO 2020, London, UK, June 8-10, 2020. | en |
dc.description.abstract | 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. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Springer Nature | en |
dc.rights | 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. | en |
dc.rights | 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'. | en |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.subject | Triangle-free 2-matchings | en |
dc.subject | b-factors | en |
dc.subject | Extended formulation | en |
dc.subject | Polynomial-time algorithm | en |
dc.title | Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles | en |
dc.type | conference paper | - |
dc.type.niitype | Conference Paper | - |
dc.identifier.jtitle | Integer Programming and Combinatorial Optimization | - |
dc.identifier.volume | 12125 | - |
dc.identifier.spage | 280 | - |
dc.identifier.epage | 293 | - |
dc.relation.doi | 10.1007/978-3-030-45771-6_22 | - |
dc.textversion | author | - |
dc.address | Research Institute for Mathematical Sciences, Kyoto University | en |
dcterms.accessRights | open access | - |
datacite.date.available | 2021-04-14 | - |
datacite.awardNumber | JP16K16010 | - |
datacite.awardNumber | 16H03118 | - |
datacite.awardNumber | JP18H05291 | - |
datacite.awardNumber | JP19H05485 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。