Detecting graphs with induced cycles in limited-bandwidth communication networks
| dc.contributor.author | Zapp, Timothy | |
| dc.contributor.examiningcommittee | Li, Ben (Computer Science) | |
| dc.contributor.examiningcommittee | Kamali, Shahin (York University) | |
| dc.contributor.supervisor | Miller, Avery | |
| dc.date.accessioned | 2023-09-06T16:50:04Z | |
| dc.date.available | 2023-09-06T16:50:04Z | |
| dc.date.issued | 2023-08-23 | |
| dc.date.submitted | 2023-08-23T23:20:35Z | en_US |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | |
| dc.description.abstract | The subgraph detection problem is a fundamental problem in distributed algorithms that asks the nodes of a communication network G to determine if that communication network contains a specific graph P as a subgraph. Recent work in this area has largely been focused on the case where the nodes have limited bandwidth and thus cannot communicate arbitrarily, which is part of a larger movement in distributed algorithms to reduce the amount of communication that our algorithms require. We show that, if P is a graph containing an induced cycle of length at least 4, then detecting a rainbow copy of P (in terms of vertex colourings or edge colourings) takes at least Ω(n/ log n) in the CONGEST model. Motivated by this result, we go on to show that, if P is a necklace graph containing an odd cycle of length at least 5, then detecting a copy of P takes at least Ω(n/ log n) rounds in the CONGEST model. Finally, we discuss techniques for proving similar results when P is a necklace graph containing all even cycles or a 3-cycle, and highlight the difficulties in doing so. | |
| dc.description.note | October 2023 | |
| dc.identifier.uri | http://hdl.handle.net/1993/37579 | |
| dc.language.iso | eng | |
| dc.rights | open access | en_US |
| dc.subject | CONGEST | |
| dc.subject | Subgraph detection | |
| dc.subject | Distributed computing | |
| dc.subject | Induced subgraphs | |
| dc.subject | Limited-bandwidth communication networks | |
| dc.subject | Lower bounds | |
| dc.title | Detecting graphs with induced cycles in limited-bandwidth communication networks | |
| dc.type | master thesis | en_US |
| local.subject.manitoba | no | |
| oaire.awardTitle | University of Manitoba Graduate Fellowship | |
| project.funder.identifier | http://doi.org/10.13039/100010318 | |
| project.funder.name | University of Manitoba |