Back to search

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 × 9

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/7374
8429
3326384

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Shen, ShengWei. On the Parallelization of a Search for Counterexamples to a Conjecture of Erd\H{o}s. 2012. http://hdl.handle.net/11375/12491