Approximation algorithms for weighted matching

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Approximation algorithms for weighted matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102118)