McMaster University
On the Parallelization of a Search for Counterexamples to a Conjecture of Erd\H{o}s
Abstract
dc:description.abstract<p>Denote by kt(G) the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let kt(n) = \min\{kt(G)+kt(\overline{G}) \} where $\overline{G}$ denotes the complement of $G$. Let ct(n) = {kt(n)}/{\tbinom{n}{t}} and ct be the limit of ct(n) for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that ct = 21-\tbinom{t}{2} was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p>
Degree
thesis:*- Department dc:contributor.department
- Computer Science
- Year dc:date.issued
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shen, ShengWei
- Advisors dc:contributor.advisor
-
- Deza, Antoine
- Frantisek Franek, Ned Nedialkov
Subjects
dc:subject × 9Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/10220
- Dc Identifier Other
-
opendissertations/7374
8429
3326384