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.
%0 Journal Article
%1 rw-clmf-TALG10
%A Rutter, Ignaz
%A Wolff, Alexander
%D 2010
%J ACM Transactions on Algorithms
%K 3-connected_planar_graphs 3-regular_graphs bounded-degree_block_trees large_matchings maxdeg-3_graphs maximum_matchings myown
%N 1
%P article 1, 21 pages
%R 10.1145/1868237.1868238
%T Computing Large Matchings Fast
%U http://dl.acm.org/authorize?306146
%V 7
%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-TALG10,
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 = {2024-07-14T10:03:47.000+0200},
author = {Rutter, Ignaz and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/29da448ebee5964cb6d5090c71be7978b/awolff},
doi = {10.1145/1868237.1868238},
interhash = {a6e954dea056561d7cfe28e3660adc9e},
intrahash = {9da448ebee5964cb6d5090c71be7978b},
journal = {ACM Transactions on Algorithms},
keywords = {3-connected_planar_graphs 3-regular_graphs bounded-degree_block_trees large_matchings maxdeg-3_graphs maximum_matchings myown},
number = 1,
pages = {article 1, 21 pages},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/rw-clmf-10.pdf},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/rw-clmf-08-slides.pdf},
succeeds = {rw-clmf-08},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Computing Large Matchings Fast},
url = {http://dl.acm.org/authorize?306146},
volume = 7,
year = 2010
}