\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 On Maximum Matching Width}

%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 Sigve Hortemo S\ae ther and Jan Arne Telle -- {\small University of Bergen}

\noindent \underline{Jisu Jeong} -- {\small KAIST}



\vspace{2ex}

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

Tree-width and branch-width are connectivity parameters of importance in algorithm design.
In 2012, Vatshelle introduced a graph parameter, maximum matching width, defined by a branch-decomposition over the vertex set of a graph $G$, using the symmetric submodular function obtained by taking the size of a maximum matching of the bipartite graph crossing the cut.

Tree-width and branch-width have alternative definitions through intersections of subtrees of a tree,
where tree-width focuses on vertices and branch-width focuses on edges.
We show that maximum matching width combines both aspects, focusing on vertices and on edges.
Based on this we prove that given a graph $G$ and a branch-decomposition of maximum matching width $k$, 
we can solve Dominating Set Problem in time $O^*(8^k)$. This runtime beats $O^*(3^{tw(G)})$-time algorithm for tree-width 
whenever $tw(G)>1.893k$.


%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}