Аннотация

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.

Линки и ресурсы

тэги

сообщество

  • @awolff
  • @dblp
  • @fink
@fink- тэги данного пользователя выделены