\documentclass[11pt]{article}
\usepackage[russian,greek,english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large  Enumeration of Minimal Connected Dominating Sets and Minimal Connected Vertex Covers}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):  

%\noindent M. Coauthor -- {\small Other university}

P. Heggernes -- {\small University of Bergen}

P. Golovach --   {\small University of Bergen}

%\noindent \underline{N.  Speaker} -- {\small Miscatonic University}

\underline{D. Kratsch} -- {\small Universit\'e Lorraine}

\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract

Connected Dominating Set and Connected Vertex Cover are classical problems of computer science. Although the optimization and decision variants of the problems are well studied, surprisingly there is no work on the enumeration or maximum number of minimal connected dominating sets or vertex covers of a graph. We construct exact exponential enumeration algorithms for these problems for graphs classes and use the algorithms to obtain upper bounds for the number of minimal connected dominating sets and minimal connected vertex covers.
For minimal connected dominating sets, we consider some graph classes of bounded chordality. In particular, we show that all minimal connected dominating sets of an $n$ vertex chordal graph can be enumerated in time $O^*(1.7159^n)$. For split graphs, minimal connected dominating sets can be enumerated in time $O^*(1.3803^n)$, and for AT-free, strongly chordal and distance-hereditary graphs in time $O^*(3^{n/3})$. These algorithms immediately imply the corresponding upper bound for the number of minimal connected dominating sets. For minimal connected vertex covers, we show that the maximum number of minimal connected vertex covers of a graph is $O(1.8668^n)$, and these can be enumerated in time $O(1.8668^n)$. For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds $O(3^{n/3})$ on the maximum number of minimal connected vertex covers. 

%This paper is about ... Cite like that \cite{CCHPP}, \cite{Wol15}. 


%If you need a ref section, do it more or less like that : 
%\small
%\begin{thebibliography}{1}
%
%\bibitem{CCHPP}
%R.~H. Chitnis, M.~Cygan, M.~Hajiaghayi, M.~Pilipczuk, and M.~Pilipczuk.
%\newblock Designing {FPT} algorithms for cut problems using randomized
%  contractions.
%\newblock In {\em 53rd Annual {IEEE} Symposium on Foundations of Computer
%  Science (FOCS)}, pages 460--469, 2012.
%
%\bibitem{Wol15}
%P.~Wollan.
%\newblock The structure of graphs not admitting a fixed immersion.
%\newblock {\em Journal of Combinatorial Theory, Series {B}}, 110:47--66, 2015.

%\end{thebibliography}


\end{document}