Browsing Combinatorics and Optimization by Author "Webb, Kerri"
Now showing items 1-2 of 2
-
Counting Bases
Webb, Kerri (University of Waterloo, 2004)A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of ... -
Matrix Formulations of Matching Problems
Webb, Kerri (University of Waterloo, 2000)Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation ...