%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	maxclq_resume.tex
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%#! platex maxclq_resume.tex

\documentclass[a4paper]{jarticle}

\usepackage{tani_resume_last}

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

% ���ܸ줿���Ȥ�
\jptitle{���祯�꡼�������򤯹�®�ʥ��르�ꥺ�����ƤȽ���μ�ˡ�Ȥμ¹Ի�����Ӽ¸�}
% ��ʸ�����ȥ�
\etitle{A fast algorithm for solving Max-Clique problem}
% ̾��
\jpauthor{���ġ��ѹ�}
\eauthor{Hideyuki Harada}
\course{ë�����漼}
\year{17}
\abstract{%����
���祯�꡼�������NP�����°�����ȹ礻��Ŭ������Ǥ��ꡤ����ʥ���դ��Ф��ƤϷ׻����֤�����Ǽ¼��׻���ǽ�Ȥ���Ƥ��롥
���������򤯥��르�ꥺ����®�����뤳�Ȥˤ�ꡤ���ޤǲ򤱤ʤ��ä��褦�ʥ���դ�򤯤��Ȥ���ɸ�Ȥ��롥
����ե��르�ꥺ��ϱ���ʬ�������¿���οͤ����Ω�ĸ���Ǥ��롥
}

% �ǽ��������������
%\compheading
\setcounter{page}{11}

\begin{document}

% �����ȥ��ɽ��������
\maketitle

\begin{multicols}{2}

\section{�Ϥ����}
   ���祯�꡼������Ȥϡ�ñ��̵���������Ǵ�������դ�ͶƳ����ĺ������Τ�����ĺ����������Τ�Τ򸫤Ĥ����Ŭ������ΰ��Ǥ��롥\\
   ���祯�꡼�������NP�����°����Τ�¿�༰���֤ǲ򤯤��ȤϤǤ��ʤ������ؿ��ؿ�������Ǥ�Ǥ������®��������륢�르�ꥺ��γ�ȯ������Ǥ��롥\\
   �ܸ���Ǥ������ؤι����л�θ����̤�������ŵ��̿���ؤ����ıٻʶ����γ�ȯ�������르�ꥺ������®�ʥ��르�ꥺ���ȯ���뤳�Ȥ��ܻؤ���\\

\section{���}

   \subsection{����ɽ��}
   Ǥ�դΥ����$G$���Ф��ưʲ��Τ褦��ɽ����Ԥ�\\
   $V(G)$: �����$G$��ĺ������\\
   $E(G)$: �����$G$���ս���\\
   $\Gamma (p)$: ĺ��$p \in V(G)$�����ܤ���ĺ���ν��硥��˵�ȸƤ֡�\\
   $\mbox{degree}(v)$: ĺ��$v$�����ܤ���ĺ���ο��������ȸƤ֡�\\

   \subsection{ͽ���μ�}
   \noindent ���꡼��: ��������դ�ͶƳ����ĺ������\\
   ���祯�꡼��: ¾�Υ��꡼���ο���ʬ����Ǥʤ����꡼��\\
   ���祯�꡼��: ��������ĺ����������Υ��꡼��\\
   ��ͶƳ��ʬ�����: $V'\in V(G)$�ʤ�$V'$�ȡ�$E' = \{ (u, v)\in E(G) | u\in V'\wedge v\in V' \} $�ʤ�$E'$�ǹ��������$G$����ʬ�����$G' = (V', E')$\\

   �㡧\\
   \begin{picture}(75,45)
    \put( 8, 8){\circle{8}}  % hidari sita
    \put( 8,38){\circle{8}}  % hidari ue
    \put(38, 8){\circle*{8}}  % sita
    \put(38,38){\circle*{8}} % ue
    \put(68, 8){\circle*{8}}  % migi sita
    \put(68,38){\circle{8}}  % migi ue
    \put( 8,12){\line(0,1){22}}
    \put(38,12){\line(0,1){22}}
    \put(68,12){\line(0,1){22}}
    \put(12, 8){\line(1,0){22}}
    %\put(12,38){\line(1,0){22}}
    \put(42, 8){\line(1,0){22}}
    \put(42,38){\line(1,0){22}}
    \put(11,11){\line(1,1){24}}
    \put(41,11){\line(1,1){24}}
    \put(35,11){\line(-1,1){24}}
    \put(65,11){\line(-1,1){24}}
   \end{picture}
   \begin{picture}(75,50)
    \put( 8, 8){\circle*{8}}  % hidari sita
    \put( 8,38){\circle*{8}}  % hidari ue
    \put(38, 8){\circle*{8}}  % sita
    \put(38,38){\circle{8}}  % ue
    \put(68, 8){\circle{8}}  % migi sita
    \put(68,38){\circle{8}}  % migi ue
    \put( 8,12){\line(0,1){22}}
    \put(38,12){\line(0,1){22}}
    \put(68,12){\line(0,1){22}}
    \put(12, 8){\line(1,0){22}}
    %\put(12,38){\line(1,0){22}}
    \put(42, 8){\line(1,0){22}}
    \put(42,38){\line(1,0){22}}
    \put(11,11){\line(1,1){24}}
    \put(41,11){\line(1,1){24}}
    \put(35,11){\line(-1,1){24}}
    \put(65,11){\line(-1,1){24}}
   \end{picture}
   \begin{picture}(75,50)
    \put( 8, 8){\circle{8}}  % hidari sita
    \put( 8,38){\circle{8}}  % hidari ue
    \put(38, 8){\circle*{8}}  % sita
    \put(38,38){\circle*{8}} % ue
    \put(68, 8){\circle*{8}}  % migi sita
    \put(68,38){\circle*{8}}  % migi ue
    \put( 8,12){\line(0,1){22}}
    \put(38,12){\line(0,1){22}}
    \put(68,12){\line(0,1){22}}
    \put(12, 8){\line(1,0){22}}
    %\put(12,38){\line(1,0){22}}
    \put(42, 8){\line(1,0){22}}
    \put(42,38){\line(1,0){22}}
    \put(11,11){\line(1,1){24}}
    \put(41,11){\line(1,1){24}}
    \put(35,11){\line(-1,1){24}}
    \put(65,11){\line(-1,1){24}}
   \end{picture}\\
   \hspace{4.2em}(a)\hspace{6.5em}(b)\hspace{6.5em}(c)\\
   (a)����Ǥʤ����꡼��\\
   (b)���祯�꡼��\\
   (c)���祯�꡼��\\

   \begin{picture}(75,45)
    \put( 8, 8){\circle*{8}}  % hidari sita
    \put( 8,38){\circle{8}}  % hidari ue
    \put(38, 8){\circle*{8}}  % sita
    \put(38,38){\circle*{8}} % ue
    \put(68, 8){\circle{8}}  % migi sita
    \put(68,38){\circle*{8}}  % migi ue
    \put( 8,12){\line(0,1){22}}
    \put(38,12){\line(0,1){22}}
    \put(68,12){\line(0,1){22}}
    \put(12, 8){\line(1,0){22}}
    %\put(12,38){\line(1,0){22}}
    \put(42, 8){\line(1,0){22}}
    \put(42,38){\line(1,0){22}}
    \put(11,11){\line(1,1){24}}
    \put(41,11){\line(1,1){24}}
    \put(35,11){\line(-1,1){24}}
    \put(65,11){\line(-1,1){24}}
   \end{picture}
   \begin{picture}(25,45)
    \put(12,22){$\Rightarrow$ }
   \end{picture}
   \begin{picture}(75,45)
    \put( 8, 8){\circle*{8}}  % hidari sita
    %\put( 8,38){\circle{8}}  % hidari ue
    \put(38, 8){\circle*{8}}  % sita
    \put(38,38){\circle*{8}} % ue
    %\put(68, 8){\circle{8}}  % migi sita
    \put(68,38){\circle*{8}}  % migi ue
    %\put( 8,12){\line(0,1){22}}
    \put(38,12){\line(0,1){22}}
    %\put(68,12){\line(0,1){22}}
    \put(12, 8){\line(1,0){22}}
    %\put(12,38){\line(1,0){22}}
    %\put(42, 8){\line(1,0){22}}
    \put(42,38){\line(1,0){22}}
    \put(11,11){\line(1,1){24}}
    \put(41,11){\line(1,1){24}}
    %\put(35,11){\line(-1,1){24}}
    %\put(65,11){\line(-1,1){24}}
   \end{picture}\\
   �ɤ�Ĥ֤��줿ĺ���ν���$V'$�ˤ����ͶƳ��ʬ�����\\

\section{��¸���르�ꥺ��}

   \subsection{���ܥ��르�ꥺ��dfmax}
   �����ݻ����륯�꡼����$Q$�Ȥ����Ȥ���$Q$��ĺ�����Ƥ����ܤ���ĺ���ν���������������ȸƤӡ�$R$��ɽ����\\
   $R$���ĺ����Ŭ�������ӡ�$Q$���դ��ä�����ǿ����ʸ�����������$R_p$��������$Q$��$R_p$���Ф���Ʊ�ͤ�����Ƶ�Ū��Ŭ�Ѥ��롥
   $Q_{max}$�ˤϸ���ȯ���������祯�꡼����Ǻ��祵�����Τ�Τ���¸���롥\\

   �ޤ��ϸ�����������$R = V(G)$��$Q = \phi$�ǽ��������$R$��$Q$���Ф��ưʲ�������Ԥ���
   \begin{enumerate}
    \item $p\in R$�������ӽФ�
    \item $Q := Q\cup \{ p\} $
    \item $R_p := R \cap \Gamma (p)$
     \begin{enumerate}
      \item $R_p \neq \phi $ �ʤ��$R_p$��$Q$���Ф���1.���������Ƶ�Ū��Ŭ�Ѥ���
      \item $(R_p = \phi ) \wedge (\vert Q\vert > \vert Q_{max}\vert )$�ʤ�� $Q_{max} := Q$
     \end{enumerate}
    \item $R := R - \{ p\} $, $Q := Q - \{p \} $
   \end{enumerate}
   ��������$R = \phi$�Ȥʤ�ޤǷ����֤���\\

\noindent dfmax($R, Q$)\{\\
  \hspace{1em}while $R \neq \phi $ do\\
   \hspace{2em}$p:= $ a vertex in $R$;\\
   \hspace{2em}$Q:= Q \cup \{p\}$;\\
   \hspace{2em}$R_p = R \cap \Gamma (p)$;\\
   \hspace{2em}if $R_p \neq \phi $\\
    \hspace{3em}dfmax($R_p, Q$);\\
   \hspace{2em}end if\\
   \hspace{2em}else if $\vert Q\vert > \vert Q_{max}\vert $\\
    \hspace{3em}$Q_{max} = Q$;\\
    \hspace{2em}end if\\
    \hspace{2em}$Q:= Q - \{p\}$;\\
    \hspace{2em}$R:= R - \{p\}$;\\
   \hspace{1em}end while\\
 \}\\


   \subsection{���Ķ����Υ��르�ꥺ�� MCQ}
   ĺ��������Ф���̿����ϡ�ĺ������Υ��꡼���������ξ峦�Ǥ��롥\\
   ��������������������ݤ˶���̿���Ԥ��������������礫�餽�줾���ĺ�������ӽФ������ˤǤ��륯�꡼���������ξ峦�򡤳�ĺ���˳�꿶�롥\\
   ����ˤ������줿�峦���Ȥˡ�õ�����Ǥ��ڤ롥\\
   �ºݤ˸������������õ�������硤ĺ�������Ф��ƻؿ��ؿ����֤�ɬ�פ���������̿���¿�༰���֤�õ�����٤�����Ƚ�Ǥ���ǽ�Ǥ��롥\cite{Tomita}\\

   
   ���������������������Ȥ����Ƹ�������$p$�˰ʲ��ξ���������������$N[p]$�������Ƥ롥
   $(u, v) \in E(G)$ �ʤ�� $N[u] \neq N[v]$
   $N[p] = k>1$ �ʤ�� $N[v] = 1,2,\ldots,k-1$ �ʤ�$v \in \Gamma (p)$����1�Ĥ���¸�ߤ��롥

   ������������򼡿��ˤĤ��ƾ�������󤷡����������������Ƭ�����ˡ�ĺ���ζ�˵���ĺ���ˤޤ���꿶���Ƥ��ʤ����ǺǾ������������꿶�롥

\noindent NUMBER-SORT($R, N$)\{\\
  \hspace{1em}$C_{1} := \phi$; $C_{2} := \phi$;\\
  \hspace{1em}$maxno := 1$;\\
  \hspace{1em}while $R \neq \phi $ do\\
   \hspace{2em}$p:= $ first vertex in $R$;\\
   \hspace{2em}$k:= 1$;\\
   \hspace{2em}while $C_{k}\cup \Gamma(p) \neq \phi$ do\\
    \hspace{3em}$k++$;\\
   \hspace{2em}end while\\
   \hspace{2em}if $k > maxno$ then\\
    \hspace{3em}$maxno := k$;\\
    \hspace{3em}$C_{maxno+1} := \phi$;\\
   \hspace{2em}end if\\
   \hspace{2em}$N[p] := k$;\\
   \hspace{2em}$C_{k} := C_{k}\cup \{p\}$;\\
   \hspace{2em}$R := R- \{p\}$;\\
  \hspace{1em}end while\\

  \hspace{1em}$i := 1$;\\
  \hspace{1em}for $k:= 1$ to $maxno$ do\\
   \hspace{1em}for $j:= 1 $to $\vert C_{k}\vert$ do\\
    \hspace{1em}$R[i] := C_{k}[j]$;\\
    \hspace{1em}$i++$;\\
   \hspace{1em}end for\\
  \hspace{1em}end for\\
 \}\\

\noindent EXPAND($R, N$)\{\\
  \hspace{1em}while $R \neq \phi $ do\\
   \hspace{2em}$p:= $ first vertex in $R$;\\
   \hspace{2em}if $\vert Q\vert + N[p] > \vert Q_{max}\vert $\\
    \hspace{3em}$Q:= Q \cup \{p\}$;\\
    \hspace{3em}$R_p := R \cap \Gamma (p)$;\\
    \hspace{3em}if $R_p \neq \phi $\\
     \hspace{4em}NUMBER-SORT($R_p, N'$);\\
     \hspace{4em}EXPAND($R_p, N'$);\\
    \hspace{3em}end if\\
    \hspace{3em}else if $\vert Q\vert > \vert Q_{max}\vert $\\
     \hspace{4em}$Q_{max} := Q$;\\
    \hspace{3em}end if\\
    \hspace{3em}$Q:= Q - \{p\}$;\\
    \hspace{3em}$R:= R - \{p\}$;\\
   \hspace{2em}end if\\
   \hspace{2em}else return;\\
  \hspace{1em}end while\\
 \}\\

   \subsection{������θ��� CLIQUE}
   �������������߽�����󤷡���Ƭ��������ǥ��꡼���˲ä��Ƥ������ɲ�
   ����ĺ���μ�����$degree(p)$�Ȥ���Ȥ���$\vert Q\vert + degree(p) < \vert Q_{max}\vert $�Ȥʤ�ʤ��õ�����Ǥ��ڤ롥\\
   ����ȯ���������祯�꡼���������ʲ��μ�����ĺ��������������ե�������̾����롥\\
   ��������Ķ����Υ��르�ꥺ��MCQ���ɲä��ơ����르�ꥺ��ι�®����ޤ롥\\
   �ܹ�Ǥϡ��ܤ������Ƥϳ䰦���롥\\
   
\section{���르�ꥺ����ɰ�}

   \subsection{���ܥΡ��ɾ峦}
   �ƥΡ��ɤ����ľ�������䤷��õ���κݤμ꤬����Ȥ��롥�����Ǥϡ֤��ΥΡ��ɤ�ޤ९�꡼���Υ������ξ峦�פ��ղä��롥
\[
   addeg(v) = \min \{ \max \{ degree(p) |p \in \Gamma (v)\} , degree(v)\} +1
\]
   ���ʤ������ĺ�����ȤȤ��ζ�˵����ʤ�ĺ������򼡿��ˤĤ��Ƥ˹߽�����󤷡�$i > degree(node[i])$�Ȥʤ�Ǿ���$i$�򸫤Ĥ��롥
   $degree(node[i])+1$��$R \cup \{ v\}$��ͶƳ����륵�֥���դˤ����롤ĺ��$v$��ޤ�����꡼���������ξ峦�Ȥʤ롥\\
   �����������������������뤿�Ӥˤ������Ƥ�ĺ���ˤĤ��Ƶ�ᡤ�߽�Ǹ���������������󤷡���Ƭ����ĺ�������ӽФ��ƥ��꡼�����ɲä��Ƥ�����\\
   �ޤ���õ���Ǥ��ڤ�δ��ˤ���Ѥ��롥\\

\noindent SET\_ADDEG($R, addeg$)\{\\
  \hspace{1em}for all $v$ in $R$\\
   \hspace{2em}$L := \Gamma (v) \cup \{v\}$;\\
   \hspace{2em}sort $L$ with decending order by degree;\\
   \hspace{2em}while $i < degree(i) \wedge i < \vert L\vert$ do\\
    \hspace{3em}$i$++;\\
   \hspace{2em}end while\\
   \hspace{2em}$addeg(v) := degree(i)+1$;
  \hspace{1em}end for\\
 \}\\
      
   \subsection{��������������Ф���峦}
   ������$n$�Υ��꡼���Ϥ��ΥΡ��ɤ�ޤ९�꡼���������ξ峦��$n$�ʾ�ΥΡ��ɤ�$n$�İʾ�ɬ�פǤ��롥�������������Ѥ��Ƹ�������������ǤǤ��륯�꡼���������ξ峦����롥\\
   ����$+1$�Ϥ��ΥΡ��ɤ�ޤ९�꡼���������ξ峦�Ǥ��롥
   ��������������Ǽ��������$R$��$addeg$�ˤĤ��Ƥ˹߽�����󤷡�$i > addeg(R[i])$�Ȥʤ�Ǿ���$i$�򸫤Ĥ��롥$addeg(R[i])$��$R$�ˤ�������祯�꡼���������ξ峦�Ȥʤ롥\\
   ������������û���֤Ǽ¹Բ�ǽ�Ǥ���Τǡ������������礫��ĺ������������Ӥ�Ŭ�Ѥ��Ƥ�ʿ���Ǥ��롥\\
   
\noindent UPPER($up, R, addeg$)\{\\
  \hspace{1em}while $up < addeg(up) \wedge up < $ size of $R$ do\\
   \hspace{2em}$up$++;\\
  \hspace{1em}end while\\
 \}\\
   
\noindent ADDEG($R, N$)\{\\
  \hspace{1em}SET\_ADDEG(R, addeg);\\
  \hspace{1em}sort $R$ with decending order by addeg;\\
  \hspace{1em}while $R \neq \phi $ do\\
   \hspace{2em}$up := $UPPER($up, R$);\\
   \hspace{2em}$p:= $ first vertex in $R$;\\
   \hspace{2em}if $\vert Q\vert + addeg(up) > \vert Q_{max}\vert $\\
    \hspace{3em}$Q := Q \cup \{p\}$;\\
    \hspace{3em}$R_p := R \cap \Gamma (p)$;\\
    \hspace{3em}if $R_p \neq \phi $\\
     \hspace{4em}ADDEG($R_p, Q$);\\
    \hspace{3em}end if\\
    \hspace{3em}else if $\vert Q\vert > \vert Q_{max}\vert $\\
     \hspace{4em}$Q_{max} := Q$;\\
    \hspace{3em}end if\\
    \hspace{3em}$Q:= Q - \{p\}$;\\
    \hspace{3em}$R:= R - \{p\}$;\\
    \hspace{3em}$up--$;\\
   \hspace{2em}end if\\
   \hspace{2em}else return;\\
  \hspace{1em}end while\\
 \}\\
   
\section{�¹Է��}
   C++���饹�饤�֥��LEDA4.5�����Ѥ����嵭��3�ĤΥ��르�ꥺ�����������ե꡼�Υ٥���ޡ�������ս���DIMACS�٥���ޡ�������աפΤ����Ĥ��Υ���դ�򤤤���Ӽ¸���Ԥä���\\
   ���줾��Υ��르�ꥺ��ˤ��¹Ի��֤ˤĤ��Ƥϸ�Υڡ�����ɽ�ǵ���\\

   �¹ԴĶ�\\
   OS  Linux version 2.6.9-1.6\_ FC2\\
   CPU Intel Pentium4 2.66GHz\\
   RAM 1024MB\\
   ����ѥ��� gcc 3.3.3\\

 \begin{thebibliography}{1}
  \bibitem{Tomita}
   E. Tomita and T. Seki, "An efficient branch-and-bound algorithm for finding a maximum clique. " Discrete Mathematics and Theoretical Computer Science, Dijon, France, Lecture Notes in Computer Science 2731, pp.278-289 (2003). 
 \end{thebibliography}

\end{multicols}

\newpage

  \begin{tabular}{|l|c|c|c|r|r|r|r|}
   \hline
    \multicolumn{4}{|c|}{graph} & \multicolumn{4}{|c|}{used time by algorithms(sec)}\\
   \hline
    file & $\vert V\vert $ & $\vert E\vert $ & $\vert Q_{max}\vert $ & density & dfmax & MCQ & ADDEG \\
   \hline
    MANN\_a9 & 45 & 918 & 16 & 0.93 & 14 min & 0.92 & 20min\\
   \hline
    keller4 & 171 & 9435 & 11 & 0.64 & 7 min & 39.26 & 4min\\
   \hline
    c-fat200-2 & 200 & 3235 & 24 & 0.16 & 7 min & 0.07 & 0.11\\
   \hline
    c-fat200-5 & 200 & 8473 & 58 & 0.43 &  & 1.06 & 0.19\\
   \hline
    p\_hat300-1 & 300 & 10933 & 8 & 0.16 & 5.3 & 2.4 & 0.94\\
   \hline
    c-fat500-2 & 500 & 9139 & 26 & 0.07 & Over 1h & 0.4 & 0.25\\
   \hline
    c-fat500-5 & 500 & 23191 & 64 & 0.19 &  & 3.72 & 0.48\\
   \hline
    c-fat500-10 & 500 & 46627 & 1126 & 0.37 &  & 26.29 & 1.6\\
   \hline
    p\_hat1000-1 & 1000 & 122253 & 10 & 0.24 &  & 26 min & 4 min\\
   \hline
    p\_hat1500-1 & 1500 & 284923 & 11 & 0.25 &  & Over 2h & 49 min\\
   \hline
  \end{tabular}

%  \begin{tabular}{|l|c|c|c|r|r|r|r|}
%   \hline
%    \multicolumn{4}{|c|}{graph} & \multicolumn{4}{|c|}{SST size by algorithms}\\
%   \hline
%    file & $\vert V\vert $ & $\vert E\vert $ & $\vert Q_{max}\vert $ & density & dfmax & MCQ & ADDEG \\
%   \hline
%    MANN\_a9 & 45 & 918 & 16 & 0.93 &  &  & \\
%   \hline
%    keller4 & 171 & 9435 & 11 & 0.64 &  &  & \\
%   \hline
%    c-fat200-2 & 200 & 3235 & 24 & 0.16 &  &  & \\
%   \hline
%    c-fat200-5 & 200 & 8473 & 58 & 0.43 &  &  & \\
%   \hline
%    p\_hat300-1 & 300 & 10933 & 8 & 0.16 &  &  & \\
%   \hline
%    c-fat500-2 & 500 & 9139 & 26 & 0.07 &  &  & \\
%   \hline
%    c-fat500-5 & 500 & 23191 & 64 & 0.19 &  &  & \\
%   \hline
%    c-fat500-10 & 500 & 46627 & 1126 & 0.37 &  &  & \\
%   \hline
%    p\_hat1000-1 & 1000 & 122253 & 10 & 0.24 &  &  & \\
%   \hline
%    p\_hat1500-1 & 1500 & 284923 & 11 & 0.25 &  &  & \\
%   \hline
%  \end{tabular}

\end{document}

