Affordable Access

Publisher Website

Finding maximum square-free 2-matchings in bipartite graphs

Authors
Journal
Journal of Combinatorial Theory Series B
0095-8956
Publisher
Elsevier
Publication Date
Volume
96
Issue
5
Identifiers
DOI: 10.1016/j.jctb.2006.01.004
Keywords
  • Matchings
  • Hamilton Cycles
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract A 2- matching in a simple graph is a subset of edges such that every node of the graph is incident with at most two edges of the subset. A maximum 2- matching is a 2-matching of maximum size. The problem of finding a maximum 2-matching is a relaxation of the problem of finding a Hamilton tour in a graph. In this paper we study, in bipartite graphs, a problem of intermediate difficulty: The problem of finding a maximum 2-matching that contains no 4-cycles. Our main result is a polynomial time algorithm for this problem. We also present a min–max theorem.

There are no comments yet on this publication. Be the first to share your thoughts.