Back to search

University of Waterloo

Recognizing Even-Cycle and Even-Cut Matroids

Abstract

dc:description.abstract

Even-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 × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/10407

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Heo, Cheolwon. Recognizing Even-Cycle and Even-Cut Matroids. University of Waterloo, 2016. http://hdl.handle.net/10012/10407