<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T14:36:43Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/14932" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/14932</identifier><datestamp>2025-03-26T23:32:56Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Haxell, Penny</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="1f38c3a6-d3f2-40b9-873c-c9088ecf91ab" confidence="600">Graf, Alessandra</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2019-08-23T14:44:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2019-08-23T14:44:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2019-08-23</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2019-08-15</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/14932</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Let G be a graph and (V_1,...,V_m) be a vertex partition of G. An independent transversal (IT) of G with respect to (V_1,...,V_m) is an independent set {v_1,...,v_m} in G such that v_i is in V_i for each i in {1,...,m}.&#xd;
&#xd;
There exist various theorems that give sufficient conditions for the existence of ITs. These theorems have been used to solve problems in graph theory (e.g. list colouring, strong colouring, delay edge colouring, circular colouring, various graph partitioning and special independent set problems), hypergraphs (e.g. hypergraph matching), group theory (e.g. generators in linear groups), and theoretical computer science (e.g. job scheduling and other resource allocation problems). However, the proofs of the existence theorems that give the best possible bounds do not provide efficient algorithms for finding an IT. In this&#xd;
thesis, we give poly-time algorithms for finding an IT under certain conditions and some applications, while weakening the original theorems only slightly. We also give e fficient poly-time algorithms for finding partial ITs and ITs of large weight in vertex-weighted graphs, as well as an application of these weighted results.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Combinatorial analysis</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Mathematical optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algorithms</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Finding Independent Transversals Efficiently</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Haxell, Penny</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>