{"id":{"repo_id":"uvic","oai_identifier":"oai:dspace.library.uvic.ca:1828/4926"},"canonical_url":"https://search.dev.ndltd.org/etd/uvic/oai:dspace.library.uvic.ca:1828/4926","repository":{"repo_id":"uvic","name":"University of Victoria (Canada)","base_url":"https://dspace.library.uvic.ca/server/oai/request"},"display":{"title":"Applications of a Novel Sampling Technique to Fully Dynamic Graph Algorithms","abstract":"In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \\begin{enumerate} \\item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\\log^2n)$ time. For a cut $(U, V\\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \\leq x \\leq 2K$ with high probability in $O(|U|\\log n)$ time. \\item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\\text{polylog}(n))$. For each node $v$ we require memory of size $\\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \\end{enumerate}","abstract_html":"In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \\begin{enumerate} \\item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in <span class=\"etd-inline-math\">O(\\log<sup>2</sup>n)</span> time. For a cut $(U, V\\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| &lt; |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \\leq x \\leq 2K$ with high probability in $O(|U|\\log n)$ time. \\item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\\text{polylog}(n))$. For each node $v$ we require memory of size $\\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of <span class=\"etd-inline-math\">O(n<sup>2</sup>)</span>. \\end{enumerate}","abstract_has_math":true,"creators":["Mountjoy, Benjamin"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["King, Valerie D."],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-09-11","date_published":"2013-09-11","updated_at":"2026-07-24T05:52:40Z","subjects":["graph algorithm","randomized","distributed graph algorithms","spanning forest","spanning tree","cut size estimation"],"languages":["en","English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1828/4926","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.supervisor","label":"Supervisor","values":["King, Valerie D."]},{"key":"dc:creator","label":"Author","values":["Mountjoy, Benjamin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-09-11T22:05:15Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-09-11T22:05:15Z"]},{"key":"dc:date.issued","label":"Date","values":["2013-09-11"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["graph algorithm","randomized","distributed graph algorithms","spanning forest","spanning tree","cut size estimation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1828/4926"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \\begin{enumerate} \\item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\\log^2n)$ time. For a cut $(U, V\\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \\leq x \\leq 2K$ with high probability in $O(|U|\\log n)$ time. \\item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\\text{polylog}(n))$. For each node $v$ we require memory of size $\\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \\end{enumerate}"]},{"key":"dc:title","label":"Title","values":["Applications of a Novel Sampling Technique to Fully Dynamic Graph Algorithms"]}]}],"canonical_facts":{"dc:contributor.supervisor":["King, Valerie D."],"dc:creator":["Mountjoy, Benjamin"],"dc:date.accessioned":["2013-09-11T22:05:15Z"],"dc:date.available":["2013-09-11T22:05:15Z"],"dc:date.issued":["2013-09-11"],"dc:description.abstract":["In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \\begin{enumerate} \\item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\\log^2n)$ time. For a cut $(U, V\\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \\leq x \\leq 2K$ with high probability in $O(|U|\\log n)$ time. \\item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\\text{polylog}(n))$. For each node $v$ we require memory of size $\\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \\end{enumerate}"],"dc:identifier.uri":["http://hdl.handle.net/1828/4926"],"dc:language":["English"],"dc:language.iso":["en"],"dc:subject":["graph algorithm","randomized","distributed graph algorithms","spanning forest","spanning tree","cut size estimation"],"dc:title":["Applications of a Novel Sampling Technique to Fully Dynamic Graph Algorithms"],"dc:type":["Thesis"]},"updated_at":"2026-07-24T05:52:40Z"}