文章基本信息

标题：Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
本地全文：下载
作者：Kenjiro Takazawa
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：87:1-87:14
DOI：10.4230/LIPIcs.MFCS.2016.87
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We introduce a new framework of restricted 2-matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2-matching F is called U-feasible if, for each setU in U, F contains at most |setU|-1 edges in the subgraph induced by U. Our framework includes C_{ = 5. For instance, in bipartite graphs in which every cycle of length six has at least two chords, our algorithm solves the maximum C_{<=6}-free 2-matching problem in O(n^2 m) time, where n and m are the numbers of vertices and edges, respectively.
关键词：optimization algorithms; matching theory; traveling salesman problem; restricted 2-matchings; Hamilton-laceable graphs