Abstract
dc:description.abstractEven-cycle and even-cut matroids are classes of binary matroids that generalize respectively graphic and cographic matroids. We give algorithms to check membership for these classes of matroids. We assume that the matroids are 3-connected and are given by their (0,1)-matrix representations. We first give an algorithm to check membership for p-cographic matroids that is a subclass of even-cut matroids. We use this algorithm to construct algorithms for membership problems for even-cycle and even-cut matroids and the running time of these algorithms is polynomial in the size of the matrix representations. However, we will outline only how theoretical results can be used to develop polynomial time algorithms and omit the details of algorithms.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2016
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Heo, Cheolwon
- Advisor dc:contributor.advisor
-
- Guenin, Bertrand
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/10407