Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2002 Copyright 2002 University of Bonn, Department of Computer Science, Abt. V
85244

19.11.2002

Finding one of many Disjoint Perfect Matchings in a Bipartite Graph
Martin Löhnertz
[Download PostScript] [Download PDF]

We demonstrate how to find a perfect matching in a bipartite graph containing n1/2sigma3 disjoint perfect matchings in time O(n1/2m/sigma).

Last Change: 11/19/02 at 09:41:32
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V