Hi all,
in which sense is the algorithm in
graph_tool.topology.max_cardinality_matching with the heuristic=True
switch a heuristic and not exact? As I understand, it might not return a
maximum-cardinality matching even if there is one. But what about the
edge weights? Does it always return a minimum-weight matching
(respectively maximum-weight with minimize=False)? Or is this not
guaranteed?
Note that there are pitfalls to this question: eg. if all edge weights
are equal to one, then the optimal min-weight matching is empty if I do
not insist on max-cardinality. Can someone enlighten me what the
heuristic actually optimizes? Cardinality or weights? Both (in which
sense) or none (what's it good for, then)? And does it always find the
optimum for one of those two criteria?
Best,
Daniel
--
Daniel Müllner
Stanford University
Department of Mathematics
450 Serra Mall, Building 380
Stanford, CA 94305
USA
e-mail: [email protected]
http://math.stanford.edu/~muellner
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
