A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs

详细信息    查看全文

• 作者：Yusuke Kobayashi
• 关键词：Triangle-free ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B7GWV-504CNJ8-2&_mathId=mml7&_user=10&_cdi=20468&_pii=S1572528610000277&_rdoc=3&_issn=15725286&_acct=C000050221&_version=1&_user
• 刊名：Discrete Optimization
• 出版年：2010
• 出版时间：November 2010
• 年：2010
• 卷：7
• 期：4
• 页码：197-202
• 全文大小：331 K

文摘

In this paper, we consider the problem of finding a maximum weight 2-matching containing no cycle of a length of at most three in a weighted simple graph, which we call the weighted triangle-free 2-matching problem. Although the polynomial solvability of this problem is still open in general graphs, a polynomial-time algorithm is given by Hartvigsen and Li for the problem in subcubic graphs, i.e., graphs with a maximum degree of at most three. Our contribution is to provide another polynomial-time algorithm for the weighted triangle-free 2-matching problem in subcubic graphs. Our algorithm consists of two basic algorithms: a steepest ascent algorithm and a classical maximum weight2-matching algorithm, and is justified by fundamental results from the theory of discrete convex functions on jump systems.