Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!apple!genbank!bionet!ig!arizona!johnk
From: johnk@cs.arizona.edu (John Kececioglu)
Newsgroups: comp.theory
Subject: Maximum Weight Matchings in Non-Bipartite Graphs
Keywords: algorithms, references
Message-ID: <16017@megaron.cs.arizona.edu>
Date: 8 Dec 89 20:14:48 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 31

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.

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.

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.

And fourth, what is the matchings generator to implement.

Thanks in advance for any references to journal papers or conference
proceedings.
---
John Kececioglu
johnk@cs.arizona.edu or arizona!johnk.uucp
Department of Computer Science, University of Arizona, Tucson, Arizona 85721
"Through small apertures we glimpse abysses whose somber depths turn us faint."
-- 
John Kececioglu
johnk@cs.arizona.edu or arizona!johnk.uucp
Department of Computer Science, University of Arizona, Tucson, Arizona 85721
"Through small apertures we glimpse abysses whose somber depths turn us faint."