90 lines
2.9 KiB
TeX
90 lines
2.9 KiB
TeX
\begin{frame}{Table of contents}
|
|
\setbeamertemplate{section in toc}[sections numbered]
|
|
\setbeamertemplate{subsection in toc}[square]
|
|
\tableofcontents[sections={3}]
|
|
\end{frame}
|
|
|
|
\subsection{Minimum Separating Vertex Set Heuristic}
|
|
\begin{frame}{Minimum Separating Vertex Set Heuristic}
|
|
|
|
\metroset{block=transparent}
|
|
\begin{block}{}
|
|
|
|
\begin{columns}
|
|
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{tikzpicture}
|
|
\node[shape=circle,draw=black] (A) at (0,0) {$X_{j_3}$};
|
|
\node[shape=circle,draw=black] (B) at (3,0) {$X_{j_4}$};
|
|
\node[shape=circle,draw=black] (C) at (1.5,1.5) {$X_i$};
|
|
\only<2->{\node[shape=circle,fill=mLightBrown] (C) at (1.5,1.5) {$X_i$};}
|
|
\node[shape=circle,draw=black] (D) at (0,3) {$X_{j_1}$};
|
|
\node[shape=circle,draw=black] (E) at (3,3) {$X_{j_2}$};
|
|
|
|
\path (A) edge (C);
|
|
\path (B) edge (C);
|
|
\path (D) edge (C);
|
|
\path (E) edge (C);
|
|
\draw[style=dashed] (E) -- (3,4);
|
|
\draw[style=dashed] (E) -- (3.8,3.8);
|
|
\draw[style=dashed] (E) -- (4,3);
|
|
\end{tikzpicture}
|
|
\end{column}
|
|
\only<3>{
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{tikzpicture}
|
|
\node[shape=circle,fill=mLightBrown] (C) at (0,0) {$S$};
|
|
\node[shape=circle,fill=mLightBrown] (C1) at (-1,1) {$S \cup W_1$};
|
|
\node[shape=circle,draw=black] (C11) at (-2,2) {$X_{j_1}$};
|
|
|
|
\node[shape=circle,fill=mLightBrown] (C2) at (1,1) {$S \cup W_2$};
|
|
\node[shape=circle,draw=black] (C22) at (2,2) {$X_{j_2}$};
|
|
|
|
\node[shape=circle,fill=mLightBrown] (C3) at (-1,-1) {$S \cup W_3$};
|
|
\node[shape=circle,draw=black] (C33) at (-2,-2) {$X_{j_3}$};
|
|
|
|
\node[shape=circle,fill=mLightBrown] (C4) at (1,-1) {$S \cup W_4$};
|
|
\node[shape=circle,draw=black] (C44) at (2,-2) {$X_{j_4}$};
|
|
|
|
\draw (C) -- (C1) -- (C11);
|
|
\draw (C) -- (C2) -- (C22);
|
|
\draw (C) -- (C3) -- (C33);
|
|
\draw (C) -- (C4) -- (C44);
|
|
\draw[style=dashed] (C22) -- (2,3);
|
|
\draw[style=dashed] (C22) -- (2.8,2.8);
|
|
\draw[style=dashed] (C22) -- (3,2);
|
|
\end{tikzpicture}
|
|
\end{column}
|
|
}
|
|
\end{columns}
|
|
\end{block}
|
|
|
|
\only<2>{
|
|
\begin{block}{}
|
|
Choose $i\in I$ such that $\vert X_i \vert$ maximal and $G[X_i]$ does not include a clique.
|
|
\end{block}
|
|
}
|
|
|
|
\only<3>{
|
|
\begin{block}{}
|
|
Construct Graph $H_i$:\\
|
|
$H_i(X_i,E_{H_i}), E_{H_i} = \{\{v,w\} \in X_i\times X_i \vert \{v,w\} \in E \vee \exists j \neq i: v,w \in X_j\}$\\
|
|
Compute minimum separator $S$; $W_1,\dots{},W_r$ are components\\
|
|
Construct new tree decomposition
|
|
\end{block}
|
|
}
|
|
|
|
\end{frame}
|
|
|
|
\subsection{Other Algorithms}
|
|
\begin{frame}{Others}
|
|
\begin{itemize}
|
|
\item MinimalTriangulation (same principle as Minimum Separating Vertex Set Heuristic)
|
|
\item Component Splitting
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "../upperbounds"
|
|
%%% End:
|