Abstract

In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in $O(nm)$ time, where $n$ denotes the number of vertices and $m$ the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3, the bounds we achieve are known to be best possible. We also investigate graphs with block trees of bounded degree, where the $d$-block tree is the adjacency graph of the $d$-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.

Links and resources

Tags

community