Name
Abstract | ||
|---|---|---|
For planar graphs, counting the number of perfect matchings (and hence determining whether there exists a perfect matching) can be done in NC [4, 10]. For planar bipartite graphs, finding a perfect matching when one exists can also be done in NC [8,7]. However in general planar graphs (when the bipartite condition is removed), no NC algorithm for constructing a perfect matching is known. We address a relaxation of this problem. We consider the fractional matching polytope P(G) of a planar graph G. Each vertex of this polytope is either a perfect matching, or a half-integral solution: an assignment of weights from the set {0,1/2, 1}to each edge of G so that the weights of edges incident on each vertex of G add up to 1 [6]. We show that a vertex of this polytope can be found in NC, provided G has at least one perfect matching to begin with. If, furthermore, the graph is bipartite, then all vertices are integral, and thus our procedure actually finds a perfect matching without explicitly exploiting the bipartiteness of G. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30140-0_43 | ALGORITHMS ESA 2004, PROCEEDINGS |
Keywords | Field | DocType |
planar graph,bipartite graph | Perfect graph,Discrete mathematics,Combinatorics,Claw-free graph,Bipartite graph,Matching (graph theory),Trivially perfect graph,3-dimensional matching,Perfect graph theorem,Mathematics,Strong perfect graph theorem | Conference |
Volume | ISSN | Citations |
3221 | 0302-9743 | 5 |
PageRank | References | Authors |
0.52 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raghav Kulkarni | 1 | 172 | 19.48 |
| Meena Mahajan | 2 | 688 | 56.90 |