Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

An Algorithmic Study of k-Maximal Matchings
by
Brian Dean
Clemson University
Coauthors: Sandra Hedetniemi, Stephen Hedetniemi, Jason Lewis, Alice McRae

A matching is k-maximal if it admits no augmenting path with 2k or fewer vertices. We first discuss the complexity of computing bk(G), the minimum cardinality of a k-maximal matching in a graph G, and show that this problem is NP-hard for bipartite and chordal graphs but polynomial-time solvable in trees. We then show how to compute a 2-, 3-, 4-, and 5-maximal matchings in any graph in linear time, from which we obtain a simple linear-time 5/6-approximation algorithm for the maximum-cardinality matching problem in a general graph.

Date received: April 18, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-50.