Approximation algorithms for weighted matching (Q1102118)

Approximation algorithms are given for the maximum weighted matching problem in planar and other n-vertex graphs of genus \(g<n\). For a planar graph, our approximation runs in O(min\(\{\) (n/\(\epsilon)\)(log n)\({}^ 2,n/c^{1/\epsilon}\})\) time. For a graph of genus g \((0<g<n)\), the running time is \(O(n^{3/2} \log n+(g/\epsilon)n \log n)\) time, given a drawing of the graph on a surface of genus g. Here, \(\epsilon\) is the relative error demanded of the approximation and c is a fixed constant.