> I have four questions concerning algorithms for maximum weight

> matchings in non-bipartite graphs. (A matching is a selection of

> edges from an undirected graph such that no two edges touch a common

> vertex.)

> First, what is the best known algorithm for computing a maximum weight

> matching in a non-bipartite graph. Here, best is with respect to

> worst-case asymptotic time.

I don't know about best for this problem, but I have been working

on fast algorithms for the problem on sparse bipartitie graphs and the

answers may be of some help.

Assume you have nodes 1..i..n, edges 1..j..m, weight vector w,

and a matrix C of connections such that C\sub{ij} = 1 if edge j

touches node i, zero otherwise. The the problem can be stated as:

maximize \sum{i=1,n}{w\sub{i} x\sub{i}}

subject to \sum{i=1,n}{C\sub{ij} x\sub{i} \le 1 all j

x\sub{i} \ge 0 all i

(I tried to trade off between TeX rigor and readability...)

This problem could be solved as a normal linear programming

problem, but it is usually much faster to solve a related problem.

Because it is much faster, you should probably solve the dual, then

use the Kuhn-Tucker conditions to recover x\sub{i}. The dual is:

minimize \sum{j=1,m}{u\sub{j}}

subject to \sum{j=1,m}{C\sub{ij}u\sub{j}} \ge w\sub{i} all i

u\sub{j} \ge 0 all j

In the bipartite case, I can transform the problem into an

Assignment Problem, then solve it by a variation of the Hungarian

Algorithm, but I don't see offhand how to do that here. This problem

has the intuitive feel of being larger but simpler than the bipartitie

case, so you may want to do what I have done and develop a special

algorithm tailored to the problem.

> Second, which matching algorithm is the best to implement on sparse

> graphs of around 1000 vertices. Here, best does not necessarily mean

> simplest to program, but rather, fast in practise.

A one thousand node problem takes about a second on a Sun-3, for

sparse matrices. But I'm solving a different problem. Solving the

dual above shouldn't take too long, and I think that you will have no

trouble recovering the primal variables, but it may take some work

(for my case a maximal flow problem) in this case it looks like

finding a solution among the edges for which C\sub{i,j} u\sub{j} = 0

for both end points.

With sparse matrix techniques minutes should be easy, seconds

possible. I'm dealing with sparse matrices (and as I say a somewhat

different problem).

> Third, what is the best known algorithm for generating matchings in

> decreasing order of weight for a non-bipartite graph. Here, worst-case

> asymptotic time is of interest.

Huh? I can't answer this question without knowing whether you

want all solutions or just the first k. If the later, think about the convex

polytope corresponding to the feasible region of the primal problem.

Finding the other good solutions by pivoting will find keep finding

new "good" solutions and will allow you to generate a bound on the

best solution not yet seen. When you have more than k better than the

best not seen, sort them and take the best k.

If you need all solutions, this technique will find them, but

realize that that is a VERY big (exponential growth) number.

--

Robert I. Eachus

with STANDARD_DISCLAIMER;

use STANDARD_DISCLAIMER;

function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...