<?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-22T10:10:13Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/3533" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/3533</identifier><datestamp>2017-03-21T21:38:48Z</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="author" authority="c4db9b00-ca1f-4ec1-8e73-b8a3c8b59cbf" confidence="600">Hoppen, Carlos</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-01-24T19:58:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2008-01-24T19:58:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-01-24T19:58:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2008</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/3533</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This thesis is devoted to the analysis of a class of&#xd;
&#xd;
iterative probabilistic algorithms in regular graphs, called&#xd;
&#xd;
locally greedy algorithms, which will provide bounds for&#xd;
&#xd;
graph functions in regular graphs with large girth. This class is&#xd;
&#xd;
useful because, by conveniently setting the parameters associated&#xd;
&#xd;
with it, we may derive algorithms for some well-known graph&#xd;
&#xd;
problems, such as algorithms to find a large independent set, a&#xd;
&#xd;
large induced forest, or even a small dominating set in an input&#xd;
&#xd;
graph G. The name ``locally greedy&amp;quot; comes from the fact that, in&#xd;
&#xd;
an algorithm of this class, the probability associated with the&#xd;
&#xd;
random selection of a vertex v is determined by the current&#xd;
&#xd;
state of the vertices within some fixed distance of v.&#xd;
&#xd;
&#xd;
&#xd;
Given r &amp;gt; 2 and an r-regular graph G, we determine the&#xd;
&#xd;
expected performance of a locally greedy algorithm in G,&#xd;
&#xd;
depending on the girth g of the input and on the degree r of&#xd;
&#xd;
its vertices. When the girth of the graph is sufficiently large,&#xd;
&#xd;
this analysis leads to new lower bounds on the independence number&#xd;
&#xd;
of G and on the maximum number of vertices in an induced forest&#xd;
&#xd;
in G, which, in both cases, improve the bounds previously known.&#xd;
&#xd;
It also implies bounds on the same functions in graphs with large&#xd;
&#xd;
girth and maximum degree r and in random regular graphs. As a&#xd;
&#xd;
matter of fact, the asymptotic lower bounds on the cardinality of&#xd;
&#xd;
a maximum induced forest in a random regular graph improve earlier&#xd;
&#xd;
bounds, while, for independent sets, our bounds coincide with&#xd;
&#xd;
asymptotic lower bounds first obtained by Wormald. Our result&#xd;
&#xd;
provides an alternative proof of these bounds which avoids sharp&#xd;
&#xd;
concentration arguments.&#xd;
&#xd;
&#xd;
&#xd;
The main contribution of this work lies in the method presented&#xd;
&#xd;
rather than in these particular new bounds. This method allows us,&#xd;
&#xd;
in some sense, to directly analyse prioritised algorithms in&#xd;
&#xd;
regular graphs, so that the class of locally greedy algorithms, or&#xd;
&#xd;
slight modifications thereof, may be applied to a wider range of&#xd;
&#xd;
problems in regular graphs with large girth.</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">Graph Theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Probabilistic Algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Properties of graphs with large girth</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">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" lang="en">Doctor of Philosophy</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>