%0 Journal Article %1 rw-clmf-10 %A Rutter, Ignaz %A Wolff, Alexander %D 2010 %J #TALG# %K maximummatchings 3-connectedplanargraphs Largematchings maxdeg-3graphs 3-regulargraphs bounded-degreeblocktrees %T Computing Large Matchings Fast %U #AWPUBURL#rw-clmf-10.pdf %X 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.

@article{rw-clmf-10, 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(\sqrt{n}m)$ 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. \par 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 \emph{maximum} matchings in slightly superlinear time.}, added-at = {2010-04-13T09:41:23.000+0200}, author = {Rutter, Ignaz and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/259b378f6bd85a2fab669d6bec6526aad/fink}, interhash = {a6e954dea056561d7cfe28e3660adc9e}, intrahash = {59b378f6bd85a2fab669d6bec6526aad}, journal = {#TALG#}, keywords = {maximummatchings 3-connectedplanargraphs Largematchings maxdeg-3graphs 3-regulargraphs bounded-degreeblocktrees}, note = {To appear; conference version appeared at SODA'08.}, pdf = {#AWPUBURL#rw-clmf-10.pdf}, succeeds = {rw-clmf-08}, timestamp = {2010-04-13T09:41:23.000+0200}, title = {Computing Large Matchings Fast}, url = {#AWPUBURL#rw-clmf-10.pdf}, year = 2010 }