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(vnm) 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.
|Title of host publication||Proceedings 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08, San Francisco CA, USA, January 20-22, 2008)|
|Place of Publication||Philadelphia PA|
|Publisher||Society for Industrial and Applied Mathematics (SIAM)|
|Publication status||Published - 2008|