%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	tani_resume.syt �g�p��
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#! platex resume.tex
\documentclass[a4paper]{jarticle}
\usepackage{pifont}

\usepackage{url}

\usepackage{tani_resume_last,amsmath}
\usepackage{epic}
\usepackage{eepic}

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

\usepackage{amssymb}
\bibliographystyle{plain}
\usepackage{natbib}

% ���{�ꂽ���Ƃ�
\jptitle{�ʐF�����������߂�q���[���X�e�B�b�N}
% �p���^�C�g��
\etitle{A heuristic method of computing chromatic polynomials}
% ���O
\jpauthor{����@���G}
\eauthor{Takahiro Imai}
\course{�J�@������}
\year{19}
\abstract{
P.Berthome,S.Lebresne,and K.Nguyen[1]�ɂ���Đ݌v���ꂽ�ʐF������������
��A���S���Y���̎��������݂�.�A���Aclique-tree,triangulation�̃A���S���Y����Pinar Heggernes and Yngve Villanger[2]�̃A���S���Y����p���Ă���.}

% �ŏI�X�V�����̑}��
 %\compheading

\begin{document}

% �^�C�g����\��������
\maketitle

\begin{multicols}{2}
\section{�͂��߂�}
�ʐF�Ƃ͊e���_�ɐF��h��Ƃ��A�אڂ���ǂ�2���_���قȂ�F�œh�邱�Ƃł���.
�ʐF�������Ƃ͖����O���t�Ń��[�v�̖����O���t�ƁA�F�̐����^����ꂽ�Ƃ��A
���̃O���t�̈قȂ�ʐF�̐��ł���A�ʐF�����������߂���͐����グ���̈��
�ł���.

�{�����ł�P.Berthome,S.Lebresne,and K.Nguyen�ɂ���Đ݌v���ꂽ�ʐF������
�v�Z�A���S���Y���̎��������݁A�܂��A��N�������ꂽ���@�p�i���̃v���O�������
�����ȃv���O�����̊J����ڎw��.

  2�߂ł͒�`�ɂ��āA
  3�߂ł̓A���S���Y�����āA
  4�߂ł͑O�߂Ŏg�p���Ă���choice function�ɂ��āA
  5�߂ł͔�r�����ɂ��ĉ������.\\


\section{��`}
  \subsection{�L���\�L}
   �C�ӂ̃O���tG�ɑ΂��Ĉȉ��̂悤�ɕ\�L���s��\\
   P(G,\(\lambda\) ):�ő� \(\lambda\)�F�g�������́A�O���tG�̍ʐF������\\
   G+e : �O���tG�ɕ�e��������\\
   G/e : �O���tG���e�ŏk�񂵂��O���t \\

  \subsection{chordal graph}
   ������3���傫��induce�����T�C�N�����Ȃ��O���t\\

  \subsection{triangulation}
   G=(V,E)��triangulation�Ƃ�G'=(V,E \(\cup\)F)��chordal�O���t�ɂȂ�悤��
�ӏW��F	\\		    

  \subsection{clique-tree}
   chodal�O���t \(G\) ��clique tree�͎��̂悤��
   \(tree \ T=(\mathcal{V,E})\) �ł���
   \par

   | \(\mathcal{V}={C_1,C_2,\dots,C_j}\) �� \(G\) �̋ɑ�N���[�N�̏W��\par
   | \(G\)�̑S�Ă̒��_ \(v\)�ɂ��āA\(v\)���܂ދɑ�N���[�N��
   \(T\)��subtree��induce����

��:\\
  \begin{picture}(200,50)
    \put(40,20){\circle*{6}}
    \put(50,10){\circle*{6}}
    \put(70,10){\circle*{6}}
    \put(90,10){\circle*{6}}
    \put(50,30){\circle*{6}}
    \put(70,30){\circle*{6}}
    \put(90,30){\circle*{6}}
    \put(40,20){\line(1,1){10}}
    \put(40,20){\line(1,-1){10}}
    \put(50,10){\line(0,1){20}}
    \put(50,10){\line(1,1){20}}
    \put(50,10){\line(1,0){40}}
    \put(50,10){\line(2,1){40}}
    \put(50,30){\line(1,-1){20}}
    \put(50,30){\line(1,0){40}}
    \put(50,30){\line(2,-1){40}}
    \put(70,30){\line(0,-1){20}}
    \put(70,30){\line(1,-1){20}}
    \put(70,10){\line(1,1){20}}
    \put(110,18){\line(1,0){5}}
    \put(110,22){\line(1,0){5}}
    \put(115,18){\line(0,-1){3}}
    \put(115,22){\line(0,1){3}}
    \put(115,25){\line(2,-1){10}}
    \put(115,15){\line(2,1){10}}
    \put(140,20){\circle*{6}}
    \put(160,20){\circle*{6}}
    \put(180,30){\circle*{6}}
    \put(180,10){\circle*{6}}
    \put(140,20){\line(1,0){20}}
    \put(160,20){\line(2,1){20}}
    \put(160,20){\line(2,-1){20}}
    
    \put(37,24){a}
    \put(47,34){b}
    \put(67,34){c}
    \put(87,34){d}
    \put(87,0){e}
    \put(67,0){f}
    \put(47,0){g}
    \put(130,24){abg}
    \put(165,18){bcfg}
    \put(170,34){cdfg}
    \put(170,0){bcef}
  \end{picture}
  \begin{center}
    ���}��clique-tree
  \end{center}

  \subsection{augumented clique tree}
    \noindent graph \(G=(V,E)\)
    \par
    \noindent \(F\): \(G\)��minimal triangulation
    \(T=(\mathcal{V,E})\)
    \par
    \noindent \(tree \ T=(\mathcal{V,E})\): \(G'=V,E \cup F\)��clique tree
    \par
    \noindent ���̂Ƃ��A\(\phi\)�͎��̂悤�ɒ�`���ꂽ\(F\)��subset�ɂ��
    \(\mathcal{E}\)��labeling�ł���A\(F\)�̂��߂�\(G\)��augumented clique tree ��\(T=(\mathcal{V,E},\phi)\)�Ƃ���.\\
    \hspace{3em}\ \(\phi(V_i,V_j)=F \cap E(G'[V_i,V_j])\)
\\
 \subsection{thickness}
   \subsubsection{triangulation \(F\)��thickness}
    \noindent graph \(G=(V,E)\)
    \par
    \noindent \(F\): \(G\)��minimal triangulation\\
\noindent \(Th(G,F)���O���tG,triangulation F ��thickness�Ƃ���.\)�@\\
   �@\hspace{3em}\( Th(G,F)= \textstyle\max\limits_{(V_i,V_j) \in \mathcal{E}}
|\phi(V_i,V_j)| \)
\\
   \subsubsection{graph \(G\)��thickness}
   \noindent \(G\)��thickness��\(Th(G)\)�ƒ�`����.\\
   \hspace{3em}   \( Th(G)= \textstyle\min\limits_{F \ a \ triangulation \ of \ G}
   Th(G,F)  \)

   \section{�A���S���Y��}
    \subsection{��\�I�ȍʐF������}
     \textbf{Empty graph}\hspace{8mm}\(P(\Bar{K_n},\lambda)=\lambda^n\)
     \par 
     \textbf{Complete graph} \ \(P({K_n},\lambda)=
     \lambda^{(n)}=\displaystyle \prod_{i=0}^{n-1}(\lambda-i)\) 
     \par 
     \textbf{Trees}\hspace{22mm}\(P({T_n},\lambda)=\lambda(\lambda-1)^{n-1}\)
     \par
     \textbf{Chordal graph}\hspace{6mm}\(P(G,\lambda)=
     \frac{\textstyle\prod\limits_{i=1}^{k} \lambda^{(|V_i|)}}
     {\textstyle\prod\limits_{(V_i,V_j) \in \mathcal{E}}
     \lambda^{(|V_i \cap V_j)|}}\)
     
   \subsection{��{�A���S���Y��}
    �^����ꂽ�O���t�����S�O���t�ɂȂ�܂ŁA�ӂ̒ǉ��A�ӂ̏k����J��Ԃ�
�ʐF�����������߂�.\\
    \\
    \noindent
    ���́@�O���tG\\
    �o�́@�O���tG�̍ʐF������\\ \\ 
    step 1 ~ �O���tG�����S�O���t \(k_n\)�Ȃ�� \(\lambda^{(n)}\)��Ԃ�\\ \\
    step 2 ~ ���S�O���t�ł͂Ȃ��Ƃ�\\
        \hspace{5mm} step 2.1 ~e \(\notin E,G_1=G+e ~and~ G_2=G/e\)
     \\
        \hspace{5mm} step 2.2~ �O���t\(G_1,G_2��step1��\)\\
    \\
    Primitive-Chromatic(G) 
    \\
    if G is a coplate graph \(K_n\) ~ then~ Return~ \(\lambda^{(n)}\)
    \\
    Let e \(\notin E,G_1=G+e~ and~ G_2/e\)
    \\
    ~~ \(P_1 \leftarrow Primitive-Chromatic(G_1)\)
    \\
    ~~ \(P_2 \leftarrow Primitive-Chromatic(G_2)\)
    \\
    ~~  \( Return P_1 + P_2\)\\ \\

   \subsection{clique-tree��p�����A���S���Y��}
    �^����ꂽ�O���t��qlique tree�𗘗p���A�O���t��chodal�O���t�ɂȂ�܂ŁA�O���t�̕����A�ӂ̒ǉ��A�ӂ̏k����J��Ԃ��ʐF�����������߂�.\\
    \\
    \noindent
    ���́@�O���tG,G��clique tree \(T\)\\
    �o�́@�O���tG�̍ʐF������\\ \\
    step 1 ~ �O���tG��chordal�O���t�Ȃ�� Return\\ \\
    step 2 ~ clique tree�����܂������ł���ӂ����݂��Ȃ��Ȃ��step3��\\ \\
    \hspace{5mm}step ~  2.1 �O���tG�𕪊�����step1��\\ \\
    step 3 ~ \(Let e = ChoiceFuncion(G,T)\)\\ \\
    \hspace{5mm}step ~ 3.1 \(G_1=G+e,G_2=G/e\)\\ \\
    \hspace{5mm}step ~ 3.2 �ӂ��̃O���t��step1��\\
    
    \(P(G,T)\)
    \par
    1 \ \textbf{begin}
    \par
    2\hspace{5mm} \mbox{\textbf{if} \(G\) is trianglated \textbf{then Return}}
    \par
    3\hspace{5mm} \textbf{if} \( \exists e \in T \) such that \( \phi (e)= \varnothing \)
    \par
    4\hspace{10mm} Let \(G_1,T_1,G_1,T_2\) and \(K_r\)
    \par
    5\hspace{10mm} \(P_1\leftarrow\) P \((G_1,T_1)\)
    \par
    6\hspace{10mm} \(P_2\leftarrow\) P \((G_2,T_2)\)
    \par
    7\hspace{10mm}\textbf{return} \(P_1 \times P_2/P(K_r)\)�@�@
    \par
    8\hspace{5mm} Let \(e=\ \mbox{ChoiceFunction}\ (G,T) \)
    \par
    9\hspace{10mm} \(G_1=G+e\ \mbox{, and the resulting}\ T_1=T\)
    \par
    10\hspace{10mm} \(G_2=G \diagup e\ \mbox{, and the resulting}\ T_2\)
    \par
    11\hspace{10mm} \textbf{return} P\((G_1,T_1)+ \)P\((G_2,T_2)\)
    \par
    12 \ \textbf{end}\\
    
 \section{ChoiceFunction}
   \subsection{��삳��̍H�v}
      3.3�ɏ�����Ă���step3�͊�{�A���S���Y���̍l�����ł���A�o�������
      step2���s�����Ƃō����ɂȂ��Ă���.clique-tree��p�����A���S���Y��
      ��8�s�ڂɏ����Ă���ChoiceFunction�̑I�ѕ��ɂ���āAstep2�ւ������
      �\���������鎖�ō����ɂȂ�.
      �����ŁA��c�����label�ɑ����g���Ă���O���t�̕ӂ�I�΂��鎖�ɂ��Ă���.
   \subsection{��삳��̃A���S���Y���Ƃ̈Ⴂ}
      ����Aclique-tree�������subtree�̒��_�������������Ȃ�قǁA�v�Z������
      �ɂȂ邱�Ƃ��m���Ă����̂ŁA���͕�����̂Q��subtree�̒��_����
      �Ȃ�ׂ��������Ȃ�悤clique-tree�̕ӂ�I�сA���̕ӂ�labl�̒�����
      clique-tree�̕ӂ�label�ɑ����g���Ă���O���t�̕ӂ�I�΂��鎖�ɂ���
      ��������.
\end{multicols}
 \section{��r����}
   \subsection{�������@}
   �EC++�N���X���C�u����LEDA5.1 �𗘗p���C��L�̐V�����A���S���Y�����������A
   ��{�A���S���Y���Aclique tree�쐬�ド���_���ɕӂ�I�ьv�Z����v���O�����A
   ��삳��̃v���O�����͋��N�̃��m�𗘗p.\\
   �E���_20�ɑ΂��A�����Ӗ��x�̃O���t��10�񎎍s���A���s���Ԃ���triangulation
   �쐬�y��clique tree�쐬�Ɏg�p�������Ԃ��Ȃ������ώ��Ԃ��Ƃ�A�T�̕Ӗ��x��
   �΂����s����.\\
   �E���s��\\
   OS:Linux version 2.6.17-1.2442 FC4\\
   CPU:Intel Pentium4 2.66GHz\\
   RAM:1024MB\\
   �R���p�C��:gcc 4.0.2

   \subsection{��������}
\begin{table}[htb]
\begin{center}
\begin{tabular}{c|c|c|c|c|c}
\hline
\multicolumn{6}{c}{���_20}\\
\hline\hline
\multicolumn{1}{c|}{�Ӗ��x} & 10.00 & 30.00 & 50.00 & 70.00 & 90.00\\
\hline
time(s):��{�@& {7200�ȏ�}&{7200�ȏ�} &{7200�ȏ�} &{625.74} & {0.43} \\
\hline
time(s):ch(G,T) & & & & &\\
ChoiceFunction:ramdam & 42.15 & 213.43 & 363.34 &44.24 & 0.18 \\
\hline
time(s):ch(G,T) & & & & &\\
ChoiceFunction:2007 & 0.04 & 26.09 & 46.36 & 9.20 & 0.11 \\
\hline
time(s):ch(G,T) & & & & &\\
ChoiceFunction:2008 & 0.02 & 119.00 & 180.32 & 34.43 & 0.16\\
\hline
thickness�@& 3.8 & 4.4 & 4.1 & 3.7 & 2.1 \\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{multicols}{2}



\section{����̉ۑ�}
\noindent �E
�v���O�����S�̂̌������l���Atriangulation��clique-tree���쐬����A���S���Y����
 �H�v��������.\\

\begin{thebibliography}{8}
\bibitem{Berthome}  P.Berthome,S.Lebresne,and K.Nguyen.
 Computation of chromatic polynomials using triangulations and clique trees. : 
wg 2005 - 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Metz, France, June 23-25, 2005 
: \url{http://www.lri.fr/Rapports-internes/2005/RR1403.pdf}

\hspace{10em}\bibitem{pinar}  Pinar Heggernes and Yngva Villanger.
 Efficient Implementation of a Minimal Triangultion Algorithm. 
Proceedings ESA 2002 - 10th European Symposium on Algorithms, Rome, Italy, September 2002. Springer Verlag, Lecture Notes in Computer Science 2461, pages 550-561. 
: \url{http://www.ii.uib.no/~pinar/LB-treedec.pdf}

\hspace{10em}\bibitem{Yngve}  Yngve Villanger. 
Efficient Minimal Triangulation of Graphs by Using Tree Decompositions,
 Master's Thesis. 
Department of Informatics, University of Bergen,Norway, 2002.
: \url{http://www.ii.uib.no/~yngvev/publications/Master_Thesis.pdf}
\end{thebibliography} 
	
\end{multicols}
\end{document}
