-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdefense-announcement.tex
93 lines (64 loc) · 2.01 KB
/
defense-announcement.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
\documentclass{article}
\input{project-info}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{float}
\usepackage{listings}
\usepackage{xcolor}
\usepackage[margin=0.7in]{geometry}
\usepackage{changepage}
\colorlet{grey}{gray!120}
\pagenumbering{gobble}
\begin{document}
\begin{center}
\includegraphics[width=0.3\textwidth]{media/ci-logo.png}\\
\hfill\break
\LARGE
\textbf{\color{grey}Computer Science Master Thesis Presentation}\\
\hfill\break
\hfill\break
\Large
{\bf \thesistitle}\\
\vspace{5mm}
\large
{\bf \studentname}\\
\vspace{5mm}
\large
\textit{ Examination Committee:\\
{\bf \advisorname} (Advisor), {\bf Dr. Ivona Grzegorczyk}, {\bf
Dr. Jason Isaacs}}\\
\hfill\break
\end{center}
\begin{adjustwidth}{1in}{1in}
\textit{\bf Abstract:}\\
\vspace{3mm}
\normalsize
\noindent Indeterminate strings have received considerable attention
in the recent past. This attention is due to their applicability in
bioinformatics, and to the natural correspondence with undirected
graphs. One aspect of this correspondence is the fact that the
minimum alphabet size of indeterminates representing any given
undirected graph equals the size of the minimal clique cover of this
graph. This paper first considers a related problem: characterize
$\Theta_n(m)$, which is the size of the largest possible minimal
clique cover (i.e., an exact upper bound), and hence alphabet size of
the corresponding indeterminate, of any graph on $n$ vertices and $m$
edges. We provide improvements to the known upper bound for
$\Theta_n(m)$. Recent results also provide an algorithm
which finds clique covers in polynomial time. We build on this result
with a heuristic for vertex sorting which significantly improves their
algorithm's results, particularly in dense graphs.
\end{adjustwidth}
\hfill\break
\begin{center}
\LARGE
{\bf 2:00 pm, Thursday, May 3\textsuperscript{rd}, 2018\\
Sierra Hall 1111}\\
\vspace{15mm}
\large
{\bf All students and faculty are invited}\\
\hfill\break
\small
{\it An Academic Affairs Event}
\end{center}
\end{document}