21

0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

������������ ������������������� ������ �!���"�$#� �� &%'�(�)���+*,���!- �.#/�0��*1#2� 34#5*6�$�6#879�0�:��- ; <0*6�:��= *?>

@BADCFEHGI@BJLKMJLN @9EHGCFEOG'PQCRA:SMG:NMC

TVUXWZY\[^]5_/`�acbedf_eg\b/_ TVUOW Y\[c]5_e`�ahbedi_/g\be_j�k _�l k diUZah]5mH]5_&n�g\dfoO_e`�pqdf]sr ntg^dfoX_/`�pqdf]srBUOuwvsxixfdig\UOdipTVUXxf[\Wzy\[\p/{Ml}|(~����c��� n�`�y�mHg�mL�RT k mOW Y\mOdi�Xg�{^vF���c���X�^�

�����8�2�/�h����B�}���8�F����� ���: �¡£¢F ���¢q¤�¥¦�D�F§h¤¨�+¥&¤��©�L�F¤��ª�Z�F§��"�� X���8�« �¬�¤��L­ �£�©�s�s¢R�©®h¯��s�8���s­X�±°

�s�8¥.�©�!¤ ¢R H ��s�8�9�s¡h¤��h�£�©��� �s¢F����¤��£�9�©��¤�¯£�£�ª�£��¢F�8²5�F�� ��h¤�³6¢R�©�£��´�¢R�8�s¡\�8²5�F��µ��8³�­�´6�©��F§��¦¡£¢R�8�s�8�£²5�& �¬$¤��H­0¶c�£���s�¦�O¯£¥t®\��¢· �¬¸¬i¤��©³�°��s�s �¡�¬¹¤��©³©¯�¢R�8��¤��£�º¢F��¡c¤���¢R�+ �¬Q�s­X�s�s�8¥�� X���8��¤��£�&²5 �¥¦¥t¯h�£�©²�¤¨�F�� ��»²R§£¤��£�£�8³©��¼�½+¯�¢6¡h¢F ���¢R¤�¥¦�w¤¨¢F�D¬¹¯£³©³�­¾�£�©�s�s¢q��®h¯��s�8��´�§h¤8µ�� �¡£�F�©¥¦¤�³)�F�ª¥}�}¤��£�B�s¡h¤�²5�&²5 �¥¦¡h³��5¿�����­�´M¤��h�B�©³©³©¯£�F�s¢R¤¨�s�t�À�w  �£�ÂÁ\��¢F�8�L��¥}���F§£ O�£�+¬i �¢�F§��·���8�F�©���� �¬��£ ��£¥¦¤��sÃX�©���"¬¹¤�¯£³��±°Ä�s �³���¢R¤��H�Q¡£¢R ���¢R¤�¥¦��¼

Åt���2ÆOÇhÈc�eÉiÆO�}�hÊ�ËÍÌÏÎM��Ð2ÆH���»Ñ�ÆH�8�L�eÉiÒ��2Èh�e�Ó ¼ÕÔO¼×Ö Ø Ó  �¥}¡h¯��s��¢ Ó  �¥¦¥t¯h�£�©²�¤¨�F�� ��ZÙO­X�s�s�8¥¦�sÚÜÛ+�©�F�s¢R��®h¯��s�8�ZÙX­O�s�s�8¥&�Û¾¼©Ý¨¼ÕÞ Ø ß�¢F ���¢R¤�¥¦¥&�©���¦à��8²R§£�£�ªáH¯��8�sÚ Ó  ��£²�¯�¢F¢F�8�H�Qß6¢R ���¢R¤�¥¦¥¦�©�£�Û¾¼ÕÔO¼×Ö Ø ß�¢F ���¢R¤�¥ãâ��¢R�¶c²�¤¨�F�� ���Ú äD�8³©�©¤¨®h�ª³©����­Û¾¼ÕÔO¼©Ý�å Ø ß�¢F ���¢R¤�¥æÛ«�8�R�����XÚ ç ���F§� X�� �³� ������8�Û¾¼×Ö�¼Õè Øé½+¡^��¢q¤¨�F�©���&ÙO­X�s�s�8¥¦�±Ú êh¤�¯£³��±°Ä�s �³���¢R¤��h²5�ë ¼ÕÔO¼ÕÔ Ø Û+�©�R²5¢F���s��ç�¤¨�F§��8¥¦¤¨�F�©²��±Ú ë ¢R¤¨¡h§�ìV³��� �¢R���F§h¥¦�

í�îïqðÀïqñ2òôó±õ"ðÀö�÷�÷Oø2òÀùÀïqútûýü¾÷Hñ8òÀù)þ¨ÿ��������/òôñ2üeù���î� �������������Qñ8üLú��������:ò±ñ8üeù�����! �����

Page 2: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

" #%$'&�(*),+.-./0&�1�)2$

TVUhUXY�_/`5mH]�diUXgºyM_/]43«_e_/g9] k _&g\U65\_ep�UOu�5^dipq]�`�dfy\[^]5_�5!pRrcpR]5_/W ptdip·beUXWZWZUXg\xfr�`�_emOxid87e_�5ºy�r�UX`R���mOg^d97edfg\�º] k _ g\U:5^_ep�dfg�]5U9m�beUXg�oO_eg\df_eg�]�xiUX�Odib¨mHx¸pq]�`�[\b2]5[\`q_0p�[\b k mHpzm!`qdig\�\{wm�pR]�mO`/{¸UX`»m]5`q_e_<; ac[^b k beUhUXYM_e`�mH]5dfUXg){ k U�3V_2oX_/`e{�YMUXp�_/p m Y\`qUXy\xi_/W dªutu�mO[^xf]5p�bemOg Ucb/be[\`�5\[\`qdig\� ] k _beUOW Y\[c]�mH]�diUXgZUOu] k _¾pqrhpR]5_eW>=@?ÏmO[\xª]«Uhbeb/[\`�`q_eg\b/_ep�bemOg0YM_e`q]�[\`�y ] k _txiUX�Xdfb¨mOx�pR]5`q[\b/]�[\`�_}mHgA5] k _e`�_/y�rºg\_eb/_ep�pqdf]5mH]5_»m�`�_eUO`���mOg^d97¨mL]5diUOgBUOuw] k _¦g\U65\_ep�;

B g�d95^_¨mOxÏp�UOxi[^]�diUXg�]5U&] k _tY\`�UOy\xi_/W UOu`q_eUX`q��mOg\d87edig^�&pRrhpq]5_/W pVg\U:5^_epVdfg�]5U¦] k _�5\_epqdi`q_�5xiUO�XdibemOx6pq]5`q[\b/]�[\`�_�dfpt]�U'5\_epqdi�Xg�m0Y^`�UX�X`�mOW.] k mL]}dipDCqg\UXg\W mOpFEhdfg\��u�mO[^xf]q�ô]5UXxf_e`�mOg�]HGA;JItUXgh�W mOp!E£dig^��u�mO[^xf]q�ô]5UXxf_e`�mOg�]¦Y\`�UX�O`5mOWZp»W mKEH_ g\U!mOp�pq[\WZY^]5dfUXg\pzmHy�UX[c]&] k _�Y^`�_�5^dib/]5mOy\dfxidf]sr!UOuu�mO[\xª]:Uhbeb/[\`�`q_eg\b/_�mOgA5�{ k _eg^be_O{X]�UXxi_/`5mH]�_DuÄ[^`q] k _e`:YM_e`R]5[\`qy�mH]�diUXg\p6]5Ut] k _«pq]5`q[\b/]�[\`�_«] k mH]:W�m¨rUhbebe[^`L3 k dixf_t] k _/r0`q_eUX`q��mOg\d87e_¾] k _"g\U65\_/p�;*M�_}bemOxixÏ] k _ep�_¦Y\`qUX�X`�mOW p«g\UXg\W mOpFEhdfg\��mOpV] k _/rW mKEO_�g\U&mH]q]5_/W Y^]:]5U}W mOp!E&] k _�YM_e`R]5[\`qy�_�5 pR]5`�[^b/]5[^`�_�uÄ`�UXW ] k _�b/UcUOY�_/`5mH]�dfoX_VW _/b k mOg\dfp�WZp] k mH]·`�_/xfrBUXgB] k _¦pq]5`q[\b/]�[\`�_<;

N _eW mO`!ELmOy^xfrX{�WZ_/] k U65\puÄUX`)] k _@5\_/p�df�Xg¦UOu^g^UXg\W mOp!E£dig^�·u�mH[\xf]R�±]5UOxi_e`�mOg�])Y\`qUX�X`�mOW p k m�oO_`�_/be_/dfoX_�5»xfdf]q]5xi_:mH]�]�_eg�]5dfUXgO; j�k dfp�dfp)x¹mH`��X_/xfrJ5\[\_$]5U+] k _Qp�[\Y\YMUXpqdf]5dfUXg"] k mH]6p�[\b k WZ_/] k U:5\pO3·dfxixyM_�beUOW Y\xf_�P�{MmOgA5Q3·dfxix_�P^Y^xidib/df]�xfrBb/UXg\p�d85\_e`tmOxfx�b/UXWzy\dfg�mH]�diUXg\p·UOu:] k _»gh[^Wzy�_/`e{Ï]5dfW _H{�mHgA55\[\`�mH]5dfUXgZUOu)u�mO[\xª]QUcb/be[\`q`�_/g\be_/p�;Vl}[^`«_�P^YM_e`qdi_/g\be_tp k U�3·pe{ k U�3V_2oX_/`e{^] k mH]D] k dfp«pq[\Y\YMUXp�dª]5diUOgdipzu�mHxip�_SR��/�s�<TU;SM�_'V�gW5 ] k mH]Zm9uÄ_�3¦{Dp�dfW Y\xf_0WZ_/] k U:5\p�pq[WXZbe_ºuÄUX`z] k _�_�Y�_/b/]�dfoX_,5\_/p�df�XgUOu$WZUXpR]"g\UXg^W�mOpFE£dig\�Zu�mO[\xf]R�±]�UXxi_/`5mOg�]·Y\`qUX�X`5mHW p/{�mOgW5�m¨oXUXd85�] k _zbeUXW�y\dig�mL]5UX`qd¹mOx)Y^`�UXy\xf_eWg\UO]�_�5ÍmOyMU�oX_<;9vsg ] k dfp�Y�mHY�_/`e{�3«_D5\dipqbe[\pqpz]43VU�pq[\b k WZ_/] k U:5\p»uÄUX`Z5\_/p�df�Xg UOu·Y\`qUX�X`�mOW p] k mH]·`�_/UX`���mHg\d97/_}pqrhpq]�_eW,g\U65\_ep�;

l"g\_QWZ_/] k U:5&dip)]�Utb/UXW Y^[^]5_$] k _«pq_/][ UHu�mOxfxXpq]�`�[\b2]5[\`q_epw] k mH]�`�_/p�[\xª]6uÄ`�UXW�Y�_/`q]5[^`�y\dfg\�] k _\5\_epqdi`q_�5�pq]�`�[\b2]5[\`q_Z] y�r9�^{w�X{��c{�;^;8;¾p�diW�[\xf]5mOg\_eUO[\p�u�mH[\xf]�p�; j�k _eg){O5^_e`�dªoX_�m Y\`�UX�O`5mOWp�U9] k mH]�pq]�mH`q]5dfg\�!uÄ`qUXW mOg�r�Y\`qUX�X`�mOW pR]�mH]�__3 k _/`�_0] k _0pq]�`�[\b2]5[\`q_0dipzdfg`[ {$pq[\y\pq_�a£[\_eg�]beUOW Y\[c]�mH]�diUXg UOu+] k _�Y\`qUX�X`�mOW b�d c&mOx^3+m¨rhp»rhdf_ex95^p»Y\`qUX�X`�mOW4pq]5mH]5_/pZ3 k _e`q_�] k _�pq]�`�[\b2]5[\`q_dip¾digd[ mOgA5ebÄdidfc·`�_emOb k _ep�3·dª] k dfg m0y�UX[^gA5\_�5 g£[\WzyM_e`}UOuDpR]5_eY^p»m0Y^`�UX�X`�mOW�pR]�mH]�_\3 k _e`q_] k _�pq]5`q[\b/]�[\`�_�dfpJ]%; j�k _�beUX`q`�_eb2]5g\_/p�p&UOuQ] k dfp"WZ_/] k U:59uÄUXxfxiU�3·ptuÄ`qUXW,] k _zu�mOb2]"] k mH]}_/oO_egdfuu�mH[\xf]�pVUhbebe[^`g3 k dixf_t] k _"Y\`qUX�X`5mHW dfpV_�Pc_/be[^]�dig\�z] k _eg){^y£r.b�d c2{£] k _"Y^`�UX�X`�mOW dip+mHx83Vm�rhp�dfgmzpq]5mH]5_h3 k _e`�_}] k _}pq]�`�[\b2]5[\`q_&dfp+digD[ji k _eg^be_O{�pq[\y\pq_�a£[\_eg�]¾beUXWZY\[^]5mH]5dfUXg0UOu6] k _}Y\`�UX�O`5mOWdip��O[�mO`5mHg£]�_e_�5){�y�r`b�did c2{h]5U�`�_emOb k m�pq]5mH]5_�3 k _/`�_}] k _&pR]5`q[\b/]�[\`�_&dipL]%;

Page 3: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

B g\UO] k _e`:WZ_/] k U65�dip�]5UtW�mKEH_Vg\U"mOp�pq[\W Yc]5diUOgzmOyMUX[^]�] k _«pq]�`�[\b2]5[\`q_V] k mL]¸`�_/p�[\xª]5p�uÄ`�UXW] k _+_�Pc_eb/[^]5dfUXg�UOuÏu�mO[\xª]5p�;wvsg\pR]5_emK5){�_eg^p�[\`q_+] k mH]:] k _+Y^`�UX�X`�mOW diphCqpq]5mOy\dixfd97/dig\�kGlR×~H�nm�Tô{Xdfg�] k _uÄUXxfxiU�3·dig\�&p�_/g\p�_<;+a£]�mO`R]5dig^��uÄ`�UXW mOgºmO`qy\df]�`5mO`RrZY\`�UX�O`5mOW pq]5mH]5_H{\p�[^y\p�_�ah[^_eg�]¾b/UXWZY\[^]�mL]5diUOgUOuc] k _QY\`qUX�X`5mHWobÀmH]6] k _$uÄ[\g\b/]�diUXg\mOx�g\U65\_epHcb/UXg�oX_/`��X_/p�3·df] k dig&m·y�UX[^gA5\_�5&g£[\WzyM_e`�UOu\pR]5_/Y\p]5U�mºY\`�UX�O`5mOW pR]�mH]�_p3 k _e`q_ ] k _ZpR]5`q[\b/]�[\`�_ diph]%;BTVUO`�`�_/b/]»_�Pc_eb/[^]5dfUXg�UHuV] k _25^dipq]�`�dfy\[^]5_�5pqrhpR]5_eW ] k _/g `q_ep�[^W _/pe{DmOgA5ÍbeUOg£]�dig£[\_/pZ[^g£]�dixVm9p�[\y\pq_�a£[\_/g£] u�mO[\xª]zUhbebe[^`�`�_/g\be_ºYM_e`R]5[\`qy\p] k _&pR]5`q[\b/]�[\`�_H{Mdfg'3 k dib k b¨mOpq_}] k _¦b/rhb/xi_¦UOu¸b/UXg�oX_/`��X_/g\be_»`�_eYM_¨mL]5p�;

vsg&] k _D`�_/pq]¸UHu^] k dip�Y�mOYM_e`e{q3V_DuÄUX`�W�[\x¹mH]�_¸] k _Q]43«U"W _2] k U65\p5\_epqbe`qdiyM_�5zmHy�U�oX_«dig¦]5_/`�WZpUOu:m�[\g\dfuÄUO`�Wr5\_�V�g^df]5dfUXgBUOu�u�mO[\xª]q�±]�UXxi_/`5mOg^be_pR��/�F�qTU;Qn�p�dfg\��] k _/p�_¦W _2] k U65\p/{A3V_s5\_/p�di�Ogº]43«UuÄ[\xfxfrS5\dipR]5`qdiy\[^]�_�5){Qg\UOg\W�mHp!E£dig\��u�mO[\xf]R�±]�UXxi_/`5mOg�]»Y\`�UX�O`5mOWZp�] k mH]�W mOdig�]�mHdig�] k _Bg\U65\_ep�dfgmOg mO`�y^df]5`�mO`qr!y\[^]»beUXg^g\_eb2]5_�5`5\dipR]5`qdiy\[^]�_�5 pqrhpq]�_eW dig mº`�UhUO]5_�5 pqY�mOg\g^dig\�º]5`q_e_ mOgA5 dig m[\g\d85\di`q_eb2]5diUOg�mOx�`qdig\�^{�`�_epqY�_/b/]�dfoX_/xfrK;ut�UX`q_»pqY�_/bed^V�b¨mOxfxfrO{�UX[\`·Y\`�UO�X`5mOWZp+]5UOxi_e`�mH]5_¦mHg£r'V\g\df]�_g£[\WzyM_e`ZUOu¾u�mHdixª�±pq]�UXY u�mOdixf[\`�_/p�mOgA5 `�_eY\mOdi`qpZUHu"g\U65\_ep mOgA5 b k mOg^g\_exfp�dig ] k _v5^dipq]�`�dfy\[^]5_�5pqrhpR]5_eW>;

l"[\`ºY\`qUX�X`5mHW pBmH`�_ UXY^]�diW mOx¾dfg'] k _edf`0]5dfW _�mHgA5�pqY�mOb/_ b/UXW Y^xi_�Pcdª]srw=yx«UO] k `�_emOb kmzVWPcYMUXdig�]D3·dª] k dfg|{Db~}QcZ]5dfW _H{L3 k _e`q_S} dip�] k _�g£[\WzyM_e`0UOu&pRrcpR]5_/W g\U:5^_ep0] k mH]ºmO`q_Cq[\YWGzbÄdU;Õ_K;ª{6be[\`q`�_eg�]�xfr�g\UH]»pR]5UXY^Y�_�5`5\[^_�]�U�mºu�mOdfxª�±pq]5UOY!u�mOdixf[\`�_�c�;zl}[^`&Y^`�UX�X`�mOW1uÄUO`}`�dig^�W mOdig�]5_/g�mOg\b/_O{}dfg^u�mOb/]e{"[\pq_ep9mHp!m y�mOp�dfp!mHg£r'g^UXg\W mOp!E£dig^� u�mO[\xª]q�ô]5UXxf_e`5mHg£]0Y\`�UX�O`5mOW uÄUO`W mOdig�]�mHdig\dfg\� m `qUcUH]5_�5 p�Y�mHg\g\dig^� ]5`q_e_H{�mOgA5 `q_¨mOb k _ep0m�VWPcY�UOdig�]�3·dª] k dfg����q�W���U�K���+]5dfW _UOu¸] k _�ximH]�]�_e`�`�_emOb k dig^�Bm2VWPcYMUXdig�]�;�xVUH] k Y\`qUX�X`�mOW p�[\pq_\{Db������v��c·p�Y�mHbe_�mH]t_¨mHb k g\U:5^_mOgA5�digB_emOb k WZ_epqp5mO�O_O{A3 k _/`�_Z� dfp+] k _}]5UH]�mOx)g£[\W�y�_/`�UHu:g\U65\_/p�;

l"[\` Y\`�UX�O`5mOWÜuÄUX`Z`�dfg\��W mOdig�]�_eg�mOg^be_!dfp�UXYc]5diW mOx�dfg mOg\UH] k _/`0p�_/g\p�_<= j�k _!`�dig^��df]_epR]�mOy^xidip k _ep�p�Y\mOg\p9mL]�WZUXpR]9�Wb~}�� ��c0b/UXW W�[\g\dibemH]5dfUXg'b k mOg\g^_exip�mOgA5 ] k _ g£[\WzyM_e`�UOub k mOg^g\_exfp�y�_2]43V_/_eg pq[\beb/_epqp�dfoO_�g^U:5\_/p�dig�] k _B`�dfg\�9dfp�mH]�WZUXpq]��W;SxVUO] k ] k _epq_eCqxi_/g\�O] k GmOgA5�CF5^dix¹mL]5diUOgAG yMUX[\gW5\pºmO`�_!UXY^]5dfW�mHxtpqdig\b/_9] k _/`�_�_�Pcdfpq]ºg\_2]43VUX`FE£p�] k mH] k m¨oO_ g^U `�dig^�_eW�y�_�5A5\dig^�0UOuQxi_/g\�O] k xi_/p�p¾] k mOg �Ab�}��0��ctUX`J5\diximH]5dfUXgºxi_/p�p¾] k mOg��W;pb B pqdiWZY\xi_¦_�P^mOWZY\xf_dixfxi[\pR]5`�mH]5dfg\�t] k _·xiU�3V_/`$y�UO[\gA5ZUXg�] k _·xi_/g\�O] k dipQm}g\_/]43«UX`FE\3 k _e`q_tg\U65\_/p«mH`�_�UX`q��mOg\d87e_�5�dfgm�xfdig\_\R�?:df�X[\`q_»��mqTUi^mOgA50uÄUX`D] k _"xfU�3V_/`+y�UO[\gA5BUXg0] k _h5\dfx¹mH]�diUXg�dip+mz��y�rB��WZ_ep k g\_/]43«UX`FE3·df] k mOg�r0]43VU Y�mO`�mOxixf_ex�xfdig\_/pL5\_/xi_/]�_�5º] k mL]¾mH`�_¦m�[\g\df]L5\dipR]�mOg\b/_&mOY�mO`R]\R�?:df�X[\`�_��¨yWT~;�c

Page 4: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

b)

with dilation less than 3 is impossible

in this network

in this network; dark edge has dilation 3

An optimal-length ring embedding

An optimal-dilation ring emdedding

length less than 2(N-1) is impossibleA network where embedding a ring with

A network where embedding a ring

Figure 1: Lower bounds on length and dilation of ring embeddings

a)

l"[\`"Y^`�UX�X`�mOWZph5\d8Y�_e`¾p�di�Og\d8V�bemOg�]5xªr�uÄ`qUXW?_�Ph]�mOg�]s5\dfpq]�`�diy^[^]5_�5 mOxi�XUO`�df] k WZp�uÄUX`¾p�Y�mOgh�g\dfg\��]5`q_e_}b/UXg\pq]�`�[\b2]5dfUXgºmOgA5B`qdig\�z_/WzyM_�5A5\dfg\�Xp�;�t�UX`�_¾p�YM_ebed^V�b¨mHxixfrO{cuÄUX`D] k _¾b¨mOpq_}UOu�p�Y�mOgh�g\dfg\� ]�`�_e_»beUXg^pq]5`q[\b/]�diUXg�{�3«_z`�_/b¨mOxfx] k mH]h�¦mOxiximO� k _/`�_/]}mHxLRé�qT k m¨oX_zY^`�_epq_eg�]5_�5 mOg!_/xi_e�XmOg�]p�UOxi[^]�diUXg�y\[^]"] k _edf`¾p�UOxi[^]�diUXg�dip�u�mO[\xf]R�sdfg£]�UXxi_/`5mOg�]e{Md~; _<;f{M] k _/di`tp�UXxf[^]5dfUXgv5^Uc_/p"g\UO]}pqUXxfoO_�] k _p�Y\mOg\g\dfg\�Z]�`�_/_»`q_ebeUOgWV��X[\`�mH]5dfUXg�Y\`�UXy^xi_eW>;«ah]�mHy\dixfd97edfg\��mOxf�XUX`qdf] k W pVuÄUO`�p�Y�mOg^g\dig\��]5`q_e_&`�_8�beUOgWV��X[\`�mH]5dfUXg k m¨oO_�y�_/_eg Y\`�_/p�_/g£]�_�5�R��h{)�^{ �<Tô{M] k mL]"]5UXxf_e`�mH]5_&u�mOdixf[\`�_/p"mOp�3«_exfx¸mOp¾`�_eY\mOdi`qpUOu«y�UH] k g\U:5^_ep&mOgA5 _�5\�O_epe{�y\[^]¦] k _epq_ Y\`qUX�X`�mOW p¦mH`�_�p�df�Xg\d8V\b¨mOg�]5xªr9WZUX`�_�b/UXWZY\xi_�P9] k mOgUX[\`¾mOxi�OUX`�dª] k W�{\p�dfg\be_»[\g\xfd9EO_»UX[\`tmOxi�OUX`�dª] k W ] k _/r�mOxfxiU�3(uÄUX`·] k _»uÄUX`qW�mH]�diUXgºUOu$]�`5mOg^p�di_/g�]b/rhb/xi_epBdfg ] k _9�X`5mHY k UOu}] k _9Y�mO`q_eg�]BoHmO`�dimOy\xi_/p�;�t�UX`�_/U�oO_e`/{�] k _epq_�Y\`�UX�O`5mOWZp�b/UXg�oX_e`q�X_p�xfU�3V_/`¦] k mOg UX[\`¦mHxi�XUX`qdf] k W,dig9] k _ m¨oO_e`5mH�X_�b¨mOpq_K;2¡w_/`�xiW mOgO¢Õp}p�UOxi[^]�diUXgyR��<TQm<5A5\df]�diUXg\mOxixªr

Page 5: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

[\pq_ep}YM_e`�dfU:5^dib¦]5`5mHg\p�WZdipqp�diUOg!UOuQWZ_epqp5mO�X_/pe{O3 k dfb k `�_/p�[\xª]5p"dfg!p�df�Xg\d^V�b¨mOg�]¾beUXWZWz[\g\dfb¨mH]�diUXgU�oX_/` k _emK5O;¾l"] k _e`�Y\`qUX�X`5mHW pu3«_zmO`q_�m�3VmO`�_»UOuQmO`q_�mH]tyM_epq]�]5UOxi_e`�mOg�]�UXg\xfrB]�U ] k _&u�mHdixi[^`�_epUOuw_�5\�O_ep�UX`�UXg\xªr�] k _¦u�mHdixi[^`�_ep+mOgA5�`�_eY\mOdi`qp�UOu:g^U:5\_/p�;

?�UX`�] k _Qb¨mOpq_QUOuh`�dig^��_eWzyM_�5A5^dig\�Xp/{�] k _@5\dfpq]5`qdiy\[c]5_�5}pqUXxi[c]5diUOg\p 3«_«mH`�_Qm�3+mH`�_QUOuOR©���h{X�X��T5\U0g^UO]t]�UXxi_/`5mH]�_&u�mHdixª�±pq]�UXYBu�mOdixf[\`�_/ptUX`�`�_/Y�mOdf`�p�;t|,£_/x¹mO`Rr�mOgA5 N m¨rhg�mOxgR©���qT k m¨oO_zY\`�_/p�_/g£]�_�5mOg mOxi�OUX`�dª] k W ] k mL]«_/g£[\W _/`5mH]�_epD`�dfg\�»g^U:5\_/pe{£UXg\_tmH]«m}]5diWZ_O{Odig�] k _·UX`F5\_e`DUOum�5\_/Y^] k V�`�pR]]5`�m¨oX_e`qp5mOx$UHuVm�]�`�_/_K;sM k dixf_�] k dfp"xidfW dª]5p�] k _�xi_eg^�O] k UOuQ] k _z_eW�y�_�5A5\_�5 `�dfg\��]�U��Ab~}|�B��c2{df]�mHxixiU�3·pV] k _¤5\diximH]5dfUXg ]�U yM_¦xidig^_¨mO`+dfg>}`; j�k _¦W _/p�p5mH�X_»b/UXWZY\xi_�P^dª]sr0UOu�] k _edi`·mHxi�XUX`qdf] k Wdip0{_b~}Qc2{�mOp·WZ_epqp5mO�X_/p·beUXg�]�mHdig�m�xidipR]�UOuwg\U65\_ep�mOxf`�_¨m<5^r ]�`5m¨oX_/`�pq_�5O;gx«rD3Vm�r0UOu:b/UXg�]5`�mOpq]e{mºW _/p�p5mH�X_�Y�mOp�pqdig\�ºoX_/`�pqdiUXg UOuVUO[\`&mOxi�XUO`�df] k W¥3VUX[^x95 [\p�_ZW _/p�p�mO�X_ep&UOu«UXg\xªr�{Db������d��cp�d87e_<; N UXpq_eg\pR]5df_ k x�_/]�mHx�R��X��T k m¨oX_"Y^`�_epq_eg�]5_�5!m&p�_/xfu¹�spRrhg\b k `�UOg\d97/dig\��]�`�_/_"g\_/]43«UX`FE�UOuOV\g\df]�_pq]5mH]5_&mO[c]5UXW mH]�m�] k mH]�_�Pc_/be[^]�_»dfg�[^g\dipqUXg�uÄ`qUXW�m��XdªoX_eg�dig^df]5dimOxMpq]�mL]5_}]5U�_eW�y�_�5!m�`�dfg\��UOu5\dfx¹mH]�diUXg�mL]¦W UXpR]}] k `q_e_�UXg�] k _�]�`�_/_Z_�5\�X_/p�; B ��mHdig){)] k _�`�dig^�Bdip"uÄUX`qW _�5 UOg\_�g\U:5^_�mH]&m]5dfW _H{^[\g^xid9EH_¦digBUX[\`�mOxf�XUX`qdf] k Wo3 k _e`�_»m�`�dfg\��dip�_eW�y�_�5A5\_�5�digºm�]5`q_e_¦digºbeUOg\pq]5mOg�]�]�diWZ_K;

j�k _»Y�mOYM_e`�dip�UX`��XmOg\d97/_�5�mOp·uÄUXxixfU�3·p�;+vsg�ah_eb/]�diUXg9�c{¦3V_»pq]�mL]5_&UX[\`tmOp�pq[\W Yc]5diUOg\p¾mHgA5�XdªoX_Dm+uÄUX`�W mOxk5\_�V�g\dª]5diUOg&UHu^Y\`qUX�X`�mOW p6mHgA5&] k _edf`g\UXg\W mOpFEhdfg\�·u�mO[\xf]R�±]�UXxi_/`5mOg\b/_K;vsg�ac_eb2]5dfUXg�^{O3«_�[\p�_�] k _\V�`�pR]&W _2] k U65.5\dipqbe[\pqp�_�5�mOyMU�oX_�]5UBY^`�_epq_eg�]�m0g\UXg\W mOp!E£dfg\�0u�mO[\xª]q�±]�UXxi_/`5mOg�]Y\`qUX�X`5mHW�uÄUX`}W mOdig�]�mHdig\dfg\�0mº`�UhUO]5_�5 pqY�mOg\g^dig\�B]5`q_e_<;2M _ y^[\dix85�[\Y�UOg ] k dip¦Y\`qUX�X`5mHW�{dfgac_/b/]5dfUXg0~\{h]5U�Y\`q_epq_eg�]�m�pq]5mOy\dfxid97/dig\�&Y\`qUX�X`5mHW uÄUO`VW mOdig�]�mHdig\dfg\��m»[\g\d95^di`�_/b/]�diUXg�mHxM`qdig\�W;¸vsgac_/b/]5dfUXgvmc{A3«_¤5^dip�b/[\p�p�`�_/x¹mH]�_�5'3«UX`!EºmOgW5�W mKEO_}pqUXWZ_&b/UXg\b/xi[A5\dfg\��`�_/W�mH`!E£p�;

§ ¨©(@ªh«�1�¬ 1�$d­Z(�1�ª�®

¯L°F± ²´³:³Aµ�¶r·J¸�¹»º½¼h³

B 5\dfpq]5`qdiy\[c]5_�5 pRrcpR]5_/W beUXg^p�dipR]5p¦UOuL� g\U:5^_epe{] k mH]&mO`q_�g�mOWZ_�5Í�k¾�¿^¿8¿^¾��æ{6mHgA5 b k mOg\g\_/xip/{] k mH]�_¨mHb k b/UXg\g\_/b/]tmz[\g\d8a£[\_}Y�mOdf`VUOu�g\U65\_ep�; B ]�mOg�r0dig^pq]�mHg£]e{^_emOb k g^U:5\_"mOgA5ºb k mOg\g^_ex)dfp_edª] k _/`�Cq[\YAG�UX`�CF5\U�3·gAGW;Vl"g\xªr0[\Y�g\U65\_ep�b¨mHg�_�P^_/be[^]�_�mHb/]5dfUXg\p�]5U�W mOdig�]5mOdig�] k _s5\_epqdi`q_�5pq]�`�[\b2]5[\`q_K; B b2]5dfUXg\p}UOuVmOg [\Y g\U:5^_ZW m¨r9dfg£oOUXxfoO_�beUXWZWz[\g\dfb¨mH]�diUXg!UXg\xfrv3·df] k [^Y g^U:5\_/p] k mH]BmO`q_�C�m<5qÀ�mObe_/g�]HG�]�U�] k mL]0g\U65\_KitdU;Õ_K;ª{�beUXg^g\_eb2]5_�5'y�r [\Y b k mOg^g\_exfp�; T k mHg\g\_exfpBmO`q_y\d85\di`q_eb/]�diUXg\mOxU;@M�_ k _/g\be_2uÄUX`q] k [\p�_»dig�]5_/`�b k mHg\�X_¨mHy\xfrB] k _&]�_e`qW p_Cqg\U65\_�G�mOgA5ÁCq[\Y!g^U:5\_�G

~

Page 6: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

mOgA5º] k _¦]�_e`qW p2Cqb k mOg\g\_/x9G mOgA5eCq[\Y�b k mOg\g^_ex9GW;?ÏmOdfxª�spR]5UXY�u�mO[\xª]5p«b¨mOgºmO`qy\df]�`5mO`qdixªr�b k mOg\�O_¾] k _¾p�_/]+UOu�g\U:5^_ep�mOgW5Bb k mOg\g\_/xip/{�mOpVxfUXg\��mHp

] k _tg\U65\_/p«`q_eW mOdig�beUOg\g\_eb2]5_�5O;Jb�M _¾mOpqp�[\WZ_�beUXg\g^_eb/]�dfohdf]sr�UHu)g\U65\_epQuÄUX`Qp�dfW Y^xidib/df]sr�mOxiUOg\_K=v±u&g\U65\_ep0yM_eb/UXWZ_9Y�mO`R]5df]�diUXg^_�5){+] k _eg ] k _�g\U65\_ep0UHu¦_¨mOb k Y�mO`R]5dª]5diUOge3·dixfx·y�_�UX`q��mOg\d87e_�5dig�]�Uz] k _s5\_/p�di`q_�5ºpq]�`�[\b2]5[\`q_K;Âc N _eY�mHdi`�pVb¨mOg�xid8EO_�3·dfp�_}mH`�y\dª]5`5mH`�dixªrZb k mOg\�X_}] k _}p�_2]tUHuwg^U:5\_/pmOgA5Bb k mOg\g\_/xip�; N _eY\mOdi`qdig\��m�g\U65\_"W m�rZdfg£oOUXxfoO_"dig^df]5dimOxid87edfg\�"df]�pVpR]�mH]�_}mOY\Y\`qUXY\`qd¹mH]�_exfrO{^mHgA5`�_/Y�mOdf`�dig^��m�b k mOg\g\_/x�W m¨rBdig�oOUXxfoO_}dig\dª]5d¹mHxid97/dig\�¦] k _&pR]�mH]�_¦UOu:dª]5p�dfg\bed85\_eg�]·g\U65\_ep�;

¯L°4¯ Ã`Ä�º�Å�Ä�Æ@¶r³

B CqY\`qUX�X`5mHW�G�dfp·m�pq_/]tUOuhCRoHmO`�dimOy\xi_/p!G�mOgW5!m\V�g\dª]5_}pq_/]tUOu�CqmOb/]�diUXg\pFGA;@ÇQmOb k oHmO`qd¹mOy^xi_ k mHpm�Y\`�_�5\_�V\g\_�59g^UXg\_eWZY^]sr'5^UXW�mHdigO;*ÇQmOb k mOb2]5diUOg k mOp�] k _}uÄUX`qWv=

È �X[�mO`F5¦É Ê È pR]�mH]�_eWZ_eg�]�ÉB �X[\mO`!59dfp}m�yMUcUOxi_¨mHg!_�PcY\`q_epqp�diUOg U�oO_e`"] k _zY\`�UO�X`5mOW,oHmO`�dimOy\xf_ep�; B pq]5mH]5_/W _/g�]}[\Y�5�mH]5_/p7e_/`�UZUX`�WZUX`�_}Y\`qUX�X`�mOW oHmO`qd¹mOy\xf_ep·mOgW5�mHx83Vm�rhp�]5_/`�WZdig�mL]5_ep�[^Y�UXg�_�Pc_/be[^]�diUXgO;

�_/]0Ë y�_ZmBY\`qUX�X`5mHWv; B CqpR]�mH]�_�G�UOuÌË dip�5^_�V�g\_�5�y�r m0oHmOxi[\_�uÄUX`}_emOb k oHmO`qd¹mOy^xi_zdfg_¨mHb k g\U65\_}UOu�Ëzb�b k UOp�_egºuÄ`�UOW ] k _�5\UXW mOdig0UHuw] k _"oHmO`�dimOy\xi_�c�; B g�mOb/]�diUXgBdfp2Cq_eg�mHy\xi_�5AG�UOuË�mH]tm�pq]�mL]5_¦d8Y9] k _¦�X[�mO`F5ºUOuw] k _&mOb/]�diUXg k UOx95\p·mH]�] k mH]·pR]�mH]�_K;

B Cqpq]5mH]5_�Y\`�_�5\dibemH]5_�GzUOuAË0dip«m»yMUcUXxf_¨mOgZ_�PcY\`q_epqp�diUOgBU�oO_e`V] k _toHmO`qd¹mOy^xi_epQUOuWË; B pR]�mH]�_Y\`q_�5\dfb¨mH]�_'Í dip�mÁCnV:P^YMUXdfg£]!G!UOu�Ë dfu«uÄUX`�_emOb k pq]5mH]5_ UOu*Ëz3 k _e`�_'Í k UXx95\p/{:g\U9mOb/]�diUXg UOuË dipt_eg�mHy\xi_�5�dig!] k mH]"pR]�mH]�_K; B pR]�mH]�_�Y\`�_�5\dibemH]5_lÎædfp'CqY^`�_epq_e`RoX_�5WG�y�r�mHg�mOb/]�diUXg!UOuË d8Y_�Pc_/be[^]�dig\�B] k _�mOb/]�diUXg�{)pq]5mO`q]�dig\��uÄ`qUXW1mOg�r9pq]5mH]5_�UOu%Ë.3 k _e`q_z] k _�mOb2]5dfUXg9dip¾_eg�mOy^xi_�5 mHgA5Î k UXx85\pe{Ïrhdi_ex85\ptm�pq]5mH]5_¤3 k _e`q_ZÎ k UXx95^p�; B pq]5mH]5_»Y\`�_�5\dibemH]5_¤Îãdip_CqbexfUXp�_�5AG0dig2Ë�d8Y�Î dfpY\`q_ep�_/`qoO_�59y�rº_¨mHb k mOb2]5dfUXgºUOuwËO;

B Cqb/UXW Y^[^]�mH]�diUXgWGzUOu Ë�dfp·m�u�mOdf`e{cW�mqPcdfW�mOxMp�_�a£[\_eg\b/_zUOuwpq]�_eY\p�iMdfgº_/oX_/`qrºpR]5_eY�{MpqUXWZ_mOb2]5diUOg�dig¤Ë�] k mH]+dfp«_/g�mOy\xf_�50dfg ] k _¾b/[\`�`q_eg�]+pR]�mH]�_"dipD_�Pc_eb/[^]5_�5O;�?ÏmOdi`qg\_epqpVUOu)] k _¾pq_�a£[\_/g\be_WZ_¨mOg\p0] k mH]º_emOb k mHb/]5dfUXg'digjË'] k mH]ºdipBb/UXg�]5dig£[\UO[\p�xªrI_eg�mHy\xi_�5�mHxiUXg\� ] k _�p�_�a£[\_eg\b/_�dfp_/oO_eg�]5[\mOxixªr�_�Pc_eb/[^]5_�5O;½t!mqPcdiW mOxfdf]sr&UOuM] k _·p�_�a£[\_eg\b/_¾WZ_¨mOg^pQ] k mH]QdªuM] k _·p�_�ah[^_eg\b/_¾dip�V\g\df]�_] k _eg�g\U�mHb/]5dfUXgBdigpË�dip�_/g�mOy\xf_�5ºdigB] k _sV\g�mOxpq]5mH]5_<;

?:dfg�mOxfxfrX{wm9pq]5mH]5_�Y\`�_�5\dibemH]5_'Ï CqbeUOg£oO_e`q�X_ep�]5UKG�Ð,dfgQËÍd8Y�Ï�mHgA5yÐ,mO`�_0b/xiUXpq_�5 dfgm

Page 7: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

Ë mOgA5){pR]�mO`R]5dfg\�BuÄ`�UXW1mOg�r�pq]5mH]5_p3 k _/`�_2Ï k UOx95\p/{_/oX_/`qr b/UXW Y^[^]�mH]�diUXg�UHuË k mHp»mBpR]�mH]�_3 k _/`�_lÐ k UOx95\p�;

¯L°ÒÑ ÓÔºg¼�¶oÆ*³WÕ�¹n¼hÅ×ÖhÆ@µ�ØÒ¸ÚÙKÛ�º½ØnÜ%Ä�Æ@¼hÝÜ

�_/]½Ë�y�_�m�Y\`qUX�X`5mHW,] k mH]tW�mHdig�]�mOdfg\p�m�pq]�`�[\b2]5[\`q_Z] dig!m_5\dipR]5`qdiy\[^]�_�5�pqrhpq]�_eW>;�M�_¤V�`�pR]UXy\pq_e`RoX_"] k mH]«] k _"pq_/]+UHu�CRu�mO[\xª]q�ôuÄ`�_e_�G�pR]�mH]�_epVUHu�Ë9{^d~; _<;:] k _¾pq]5mH]5_/pg3 k _/`�_¾] k _¾pR]5`�[^b/]5[^`�_"dfp]6{�bemOg!yM_�b k mO`5mOb2]5_/`�d97/_�59y�r!m pR]�mH]�_�Y\`q_�5\dfb¨mH]�_pÍ ] k mH]¾dfp"m�VWPcY�UXdfg�]¾UOu Ë;"ah[\b k m�pR]�mH]�_Y\`q_�5\dfb¨mH]�_&d85\_eg�]�d8V�_/p+] k _vCqdfg£oHmO`qd¹mOg�]!G�UOuwËO;

M _Vg\_�Ph]¸UXy\pq_e`RoX_V] k mH]6] k _«p�_2]¸UOu�pR]�mH]�_ep�] k mH]�Ëz`q_¨mOb k _ep:dfg»] k _«Y^`�_epq_eg\b/_�UOu^u�mH[\xf]�pwbemOgyM_zb k mO`�mOb/]�_e`�d87e_�5 y�r!m0pq]5mH]5_zY^`�_�5^dib¨mL]5_ZÎã] k mL]"dip¾bexiUOp�_�5�dfg_Ë;&ac[^b k m0pR]�mH]�_zY\`q_�5\dfb¨mH]�_d95^_eg�]5d^V�_ep�] k _´CRu�mO[^xf]q�±p�Y�mHgAG�UOu0Ë;�I�UO]5_9] k mH] ] k _9u�mO[^xf]q�±p�Y�mHg dig\b/xi[A5^_ep�] k _!u�mO[\xª]q�ôuÄ`�_e_pq]5mH]5_/p�UOu6] k _}Y^`�UX�X`�mOW>;0bÀ|�_eg\b/_¤Í�Þ×Τ;�c\Ç�P^mOWZY\xi_/p�p k U�3·dfg\� k U�3 ]�Up5\_epqdi�Xg0u�mO[^xf]q�±p�Y�mHgY\`q_�5\dfb¨mH]�_ep·mOY\YM_¨mH`VdigSRÕ��T~; j�k _/p�_¦_�P^mOWZY\xi_/pV]�m<EO_"] k _¾ohdi_�3 ] k mH]�mOxfx�b/x¹mOpqp�_/p�UOuu�mO[\xª]5p+bemOgyM_�`�_eY^`�_epq_eg�]5_�5 mOp¦mOb2]5dfUXg\p¾] k mH]¦b k mOg^�X_�] k _�Y\`qUX�X`�mOW1pR]�mH]�_K;p?�UX`¾dig\pR]�mOg\b/_O{�m�u�mOdfxª�spR]5UXYu�mOdfxi[\`q_�UOuVm0g\U65\_�b¨mOg yM_�`�_eY^`�_epq_eg�]5_�5 mOp¦mHg mHb/]5dfUXg9] k mH]¦W�mH`!E£p}mOg [\Y g\U65\_ZmOp}yM_edig^�5\U�3·g){�mHgA5ºm�`�_/Y�mOdf`Vb¨mHgBy�_"`q_eY\`q_epq_eg�]5_�5!mOp+mOgBmOb2]5diUOg0W�mH`!E£p+m\5\U�3·gBg\U65\_}mHp+y�_/dig\��[\YmOgA5�`�_/dig\dª]5dimOxid87e_epQ] k _&pR]�mH]�_¦UOuw] k mH]�g\U65\_K;

M _�mH`�_¦g\U�3 `�_emK5^rB]�U �XdªoX_&m�[\g\dfuÄUO`�W×5^_�V�g\dª]5dfUXgºUOu:u�mO[^xf]q�ô]5UXxf_e`�mOg\be_<;D�6_2]�Í y�_¦] k _dig�oHmO`qd¹mOg�]VmOgA5DÎ y�_�] k _tu�mO[\xf]R�spqY�mOg�UHu�Ë`b k _/g\be_H{¦Í dip+m¤VWPcY�UXdfg�]+UOu�Ë�mOgW5_Î dipVb/xiUXpq_�5BdfgË�c�; B gW5�xi_/]�ß y�_�m�p�_2]}UOu$u�mO[\xª]"mHb/]5dfUXg\p�;�?�UX`�Ë9]5U0yM_\ß��·]5UXxf_e`5mHg£]e{M] k _�uÄUXxfxiU�3·dig^��]43«U`�_�a£[\di`q_eWZ_eg�]5p·p k UX[\x95�yM_&p�mH]5dfpFV�_�5`=

à TVxfUXp�[\`q_K=*Î(dfp�Y\`�_/p�_/`qoX_�59y�rB] k _&mOb2]5dfUXg\p�UOu�ß {à TVUXg�oO_e`��O_eg\b/_K=½Î beUXg�oO_e`��O_ept]�U�Í digpËS;j�k _�5\_�V�g\df]�diUXg�mHy�U�oX_�_eg\mOy\xi_/pDm}uÄUO`�W mOx^b/x¹mOpqp�d8V\b¨mH]�diUXg�UOu�W mOp!E£dig^�»mHgA5 g^UXg\W mOp!E£dig^�

u�mO[\xª]q�ô]5UXxf_e`5mHg\be_jR©�/�F�qT~; �_/]pË'yM_�ß"�±]5UOxi_e`�mOg�]�; v±u¤ÎâárÍ+{03V_ p�m�r ] k mH]ZË�dfp0W mOp!E£dig^�ß���]�UXxi_/`5mOg�]�;@Ç$xfp�_�b�Î`ãá>Í�c8{A3V_¦p�m�rB] k mH]*Ë�dip�g\UOg\W�mHp!E£dig\�2ß���]�UXxi_/`5mOg�]�;

M _�UXy^p�_e`RoX_DV�g\mOxixªr9] k mL]»] k __V�`qpq]zWZ_/] k U65z5\dfp�be[^p�p�_�5 dig ac_eb2]5diUOg ��dfp&uÄUX`qWz[\ximH]5_�5dig�]�_e`�WZp¦UOuD] k dfp¤5^_�V�g\dª]5dfUXg y£r9`�_�a£[\df`�dfg\�B] k mH]sÎ dfW Y^xidi_/pt] k mH]¦] k _�pR]5`�[^b/]5[^`�_Zdip}dig ] k _beUOW Y\[c]5_�5Bpq_/]L[ji\mOgA5 ] k _"pq_eb/UXgA5ºW _2] k U65_Î dipDuÄUX`�W�[\x¹mH]�_�5 y£r�`�_�ah[^di`�dfg\�»] k mH]½Î dfp«] k _pq]5mH]5_¦Y\`q_�5\dfb¨mH]�_�ä»å<æ�çk;

Page 8: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

è é ­\1�$'&�­\1�$.1�$dê ­ ëì)')p&�ª�+ í,îd­\$.$.1�$dê ïð(@ª�ª

vsg!] k dip·p�_/b/]�diUXg){¦3«_z_eWZY\xiU�r0] k _lV\`�pq]¾UOu¸] k _&]43«UD5\_/p�df�Xg!WZ_/] k U:5^p�5\dfp�be[^p�p�_�5�dig!ac_eb2]5dfUXg�"]5U�5\_/`�dªoX_¦mzg\UXg^W�mOpFE£dig\�zu�mO[^xf]q�ô]5UXxf_e`�mOg�]VY\`qUX�X`�mOW uÄUO`+W�mHdig�]�mOdfg\dig^�zmz`�UhUO]�_�5Bp�Y\mOg\g\dfg\�]5`q_e_<; N _/b¨mOxfx^] k mH]Ddig�] k dfp$W _2] k U65p3V_0V�`qpq]DbeUXWZY\[^]�_+] k _·pq_/]«UOu)mHxix^pR]5`q[\b/]�[\`�_/p«] k mH]Q`�_/p�[\xª]uÄ`�UOW�YM_e`q]�[\`�y^dig\�0] k _�5\_epqdi`�_�5 pq]5`q[\b/]�[\`�_H{wdfg9] k dfp}b¨mOpq_Zmº`qUcUH]5_�5 pqY�mOg\g\dfg\�0]5`q_e_H{�y�r mHg£rg£[\WzyM_e`·UOuwUcb/be[\`q`�_/g\be_/p¾UOu�u�mOdix©�spR]5UXY�u�mHdixi[^`�_ep+mOgA5�`�_eY\mOdi`qp�;

�_/]6[^p�`q_eY\`q_epq_eg�]w] k _Q`�UhUO]5_�5¦p�Y�mOg^g\dig\��]�`�_e_Qdfg"]5_e`qW pUHu\m2CqY�mH`�_eg�]!Gt`q_ex¹mL]5diUOg"y�_2]43V_/_egg\U65\_ep�i�_¨mOb k g\U:5^_�ñ"W mOdig�]�mHdig\p)] k _VdfgA5\_�P&UHu�df]�pwb/[\`�`q_eg�]¸Y�mH`�_eg�]:g\U:5^_Vdig¦] k _«]5`q_e_<;�ItU�3¦{XdªumOg�r�g£[\WzyM_e`QUOu�g\U:5^_epQUX`Qb k mOg\g^_exipQu�mOdfxª�spR]5UXY�{O] k _·`q_ep�[^xf]5dfg\�¦�X`5mHY k UHu�] k _�Y\mO`�_/g£]«`�_/x¹mH]�diUXgUOuQ] k _z[\Y g\U65\_ep}dfp"m�uÄUX`q_epq]¦UHu$]5`�_/_ep�;pt�UX`q_eU�oX_/`e{dªuDmOg�r9g£[\WzyM_e`}UOuQg^U:5\_/p}UX`"b k mHg\g\_exfp`�_/Y�mOdf`e{w] k _�`q_epq[\xf]�dig\���X`5mOY k UOu�] k _�Y�mH`�_eg�]�`�_eximH]5dfUXg UOu+] k _0[\Y g\U65\_/p�dip»mOxfp�U9m�uÄUX`�_/pq]¨{Y\`qU�ohd85\_�5º_¨mHb k g^U:5\_¾dig\dª]5d¹mHxid97/_ep$dª]5p�_/xfu]�U�y�_"dª]5p+U�3·gºY�mO`q_eg�]L3 k _/gºdf]+`q_eY�mHdi`�p/{�mOgA5Bxf_¨m¨oX_/pdf]�p�Y�mO`q_eg�]�[\g\b k mOg^�X_�5>3 k _eg!m�b k mOg\g\_/x�dfg\bed85\_eg�]�mH]�dª]�`�_/Y�mOdi`qp�;

M _«] k _e`q_/uÄUX`q_+Y\`�UOY�UXpq_V]5Utxi_2]:] k _VbeUOxixi_/b/]�diUXg»UOuÏmOxfx£uÄUO`�_epR]5p¸yM_«] k _+pq_/]�[.UHu�pq]�`�[\b2]5[\`q_ep] k mH]·dip�Y\`q_epq_e`qoO_�5�y�r0] k _¦Y\`�UX�O`5mOWr3V_¤5\_e`qdfoO_K;

j Up5\_e`qdfoO_}UX[\`+Y\`qUX�X`�mOW�{Ú3«_}g\_e_�5º]�U�mK5A5\`q_epqp+]43VU�Y\`qUXy\xi_/W p�;*?:df`�pq]e{ k U�3']5U k mOgA5\xf_]5`q_e_/p»] k mH]»mO`�_Zg\UO]&`�UhUO]�_�5){6] k mL]»dfpe{6]5`q_e_ep¤3·df] k g\U65\_/p¤3 k UOp�_�Y\mO`�_/g£]»g\U65\_ZUX`dCRY�mO`�_/g�]b k mOg^g\_ex8GjbÄdU;Õ_K;ª{b k mOg\g\_/x¸]5UB] k _ZY\mO`�_/g£]&g\U65\_�c¦mH`�_p5\U�3·gO; B gW5 pq_eb/UXgA5){ k U�3 ]�U k mOgA5\xf_Wz[\xª]5dfY\xi_t`�UhUO]5_�5º]�`�_/_ep�digB] k _¦�X`�mOY k UOu�] k _¦Y�mH`�_eg�]�`�_/x¹mH]�diUXgBUHu:[\Y�g\U65\_ep�;

j U p�UOxfoX_�] k _>V�`�pR]0Y\`qUXy\xf_eW�{g3V_�g\_e_�5'm WZ_eb k mHg\dipqW ]�U beUO`�`�_/b/]�_¨mOb k g^U:5\_�] k mL]k mOp�m`5\U�3·gImHg\be_/pq]5UO`�g\U65\_�UX` b k mOg\g\_/xU;�M�_�Y\`qUXY�UOp�_�]�U�b/UX`�`q_eb/] p�[^b k g\U:5^_epe{L3 k dixi_W mOdig�]�mHdig\dfg\�0] k _ pq]�`�[\b2]5[\`q_�]5U9yM_Zdig`[ {¸y�r�mHp�p�UhbedimH]5dfg\��m!beUXxfUX[\`�3·df] k _¨mHb k g\U65\_O{$mHpuÄUXxfxiU�3·p�; B p"xiUXg^�BmOp}mOxfx:mHg\be_/pq]5UO`}g\U:5^_ep¦mOgA5�b k mOg\g\_/xip}UOuDm0g\U65\_�ñ�mO`q_z[\Y){�] k _�beUOxiUX[\`UOu�ñ!dip}�X`q_e_/gO;�M k _/g mº�X`�_/_eg beUXxfUX[\`q_�5vñQ5\_/]�_eb2]5p»] k mH]&df]�p}Y�mO`q_eg�]�g^U:5\_�UX`¦b k mHg\g\_exQdfp5\U�3·g UX`¦dfp»b/UXxiUX[^`�_�5 `�_�5){Oñ9b/UXxiUO[\`�p¦df]�p�_/xfu+`q_�5O; B xipqU\{%3 k _eg m�`�_�5�beUOxiUX[\`q_�5QñQ5\_/]�_eb2]5p] k mH]�df] k mOp�g\U�`q_eW mOdig^dig\��b k dfx95\`q_eg){Ïdª]05\dipqU�3·g^p¾df]�p·Y�mO`�_/g�]"mOgW5!_exf_eb2]5p�df]5pq_exªu:`qUcUO]�i�]5U25\Up�U^{:df]&W mKEO_/p�dª]5p�_/xfu«df]�p»U�3·g�Y\mO`�_/g£]zmOgA5 beUXxfUX[\`�p&df]�p�_/xfu«�X`�_/_egO; j�k _ g\_/]»_�Y�_eb2]zUOu+] k _epq_beUOxiUX[\`qdig\��mOb2]5dfUXg\p&dip}] k mL]l3 k _/g mOg�r g\U65\_ZUX`»b k mOg\g\_/x«�XUh_ep¤5\U�3·g|bÄdfc}mOxix*5^_ep�b/_egA5^_eg�]5pUOu¸] k mH]tg\U65\_»UO`tb k mHg\g\_exwbeUXxfUX[\`�] k _eWZp�_exªoX_/p"`�_�59mOgA5�] k _/gòb�dfdfc�mOxfx5\_epqbe_egW5\_eg�]5p}UHu¸] k mL]g\U65\_"`q_ep�YM_eb2]5dªoX_exªrD5\dfp�U�3·gB] k _/di`«Y�mO`�_/g�]�;QvsgBUO] k _e`g3«UX`!5^pe{\_2oX_eg�]�[�mOxixªrBmzpR]�mH]�_"dip+`q_¨mOb k _�5

Page 9: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

3 k _/`�_¾] k _"beUOxiUX`DUOu�m�g\U65\_tdipV�O`�_e_/gBdfu6mHgA50UXg\xªrZdfu)] k _"beUOxiUX`DUOu�mOxfxMUHu6df]5p«mOg\b/_epR]5UX`+g^U:5\_/pmOgA5�b k mOg^g\_exfp�dfp��X`�_/_egO;

l"y\pq_e`qoO_�] k mH]«m}g\U65\_�UX`$b k mOg^g\_exÀ{Ú3 k UXp�_·u�mOdix©�spR]5UXYzW mKEH_epQdf]�p$b k dix85\`�_/gZb/UXxiUO[\`¸] k _/W��p�_/xfoO_ep&`�_�5�{wW m¨r9`�_/Y�mOdf`}y�_2uÄUX`�_�] k _Zb k dix95^`�_eg `�_/beUXxfUX[\`"] k _eWZp�_/xfoX_/p»�O`�_e_/gO;�vsg ] k dip}bemOp�_H{3«_»`q_�a£[\di`q_"] k mL]t[^Y�UXgº`q_eY�mOdf`+] k _¦g\U65\_¦UX`�b k mHg\g\_ex6dfg>a£[\_/pq]�diUXg�beUXxfUX[\`qp�df]5pq_exªuw`q_�5O;

col.j=green col.j=red

j detects it has no descendentssecond action (for colouring):

first action (for colouring):j repairs

j detects ancestor is down

j U�pqUXxfoO_·] k _�p�_eb/UXgA50Y^`�UXy\xf_eW�{k3V_tg\_e_�50m&W _/b k mOg\dfp�W ]�U»WZ_e`q�X_�]�`�_/_ep�;�M _�Y\`�UXYMUXpq_]5UºWZ_e`q�X_z]5`q_e_ep¦y�r �Xdªocdfg\�0Y\`q_eb/_�5\_/g\be_Z]5UB] k _�]�`�_e_p3 k UOp�_�`�UhUO] k mOp}] k _ k di� k _epR]»dfgA5\_�P�{mOp+uÄUXxfxiU�3·p�;�ÇDmHb k g\U65\_0ñZW�mOdfg�]�mOdfg\p+mz`qUcUO]VoOmHxi[\_�5\_/g\UO]�dig\�z] k _}digA5^_�PBUHuw] k _}g\U65\_"] k mL]ñ�beUXg^p�d95^_e`�p«]5U�yM_¾] k _¾`qUcUO]«UOu] k _¾pqY�mOg\g\dfg\��]�`�_e_¾beUXg�]�mHdig\dfg\��ñ�;$v±u] k _¾`qUcUO]DoHmOxi[^_¾UOu¦ñ�dfpxiU�3«_e`�] k mOg�] k _»`�UhUO]toHmOxf[\_�UHuQmOg�mK5�À�mObe_/g£]"g\U:5^_pó�{:ñBW _/`��X_/p¾dig�]�U ] k _�]5`q_e_�b/UXg�]�mOdfg\dig^�ów=�ñBmK5\UXY^]�pt] k _»`qUcUH]�oHmOxf[\_&UOu@ó�mOp�] k _�`qUcUH]�oHmOxf[\_¦UOu%ñBmOgW5!W mKEO_/phóB] k _»Y�mO`�_/g�]¾UOuñ¦;j�k _·g\_2]Q_�Y�_eb/]DUOuM] k _ep�_·WZ_e`q�X_·mOb/]�diUXg^p$dip:] k mH]Jb�d c�] k _�`qUcUH]¸oHmOxi[\_/p$UOuÏ] k _·g\U65\_/pQmOxiUXg^�¦mOxix]5`q_e_tY�mH] k pVuÄ`�UXW ] k _edf`«`qUcUO]D]5U»] k _/di`Dxi_¨m¨oO_ep+dfp+mOx^3+m¨rhpVg\UOg\dig\b/`�_emOp�dfg\�zmOgW5�b�dfdfc¸_/oO_eg�]5[�mHxixfr] k _&`qUcUH]�oOmHxi[\_}UOuw_¨mHb k g\U65\_¦dip+] k _¦digA5^_�PºUOu�] k _&`qUcUH]·UOu:dª]5p+]�`�_e_<;

par.j=jroot.j=j root.j>j

second action (for colouring):

par.j=k

and colour of j and (j,k) is greenj detects higher root via kthird action (for merging):

j detects it has no descendentsand its colour is red

Page 10: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

l"y\pq_e`qoO_�] k mH]¸W _/`��X_�mHb/]5dfUXg\pwp k UX[^x95�yM_·mOxixfU�3«_�5»]5U}_�Pc_/be[^]�_�yM_/]43«_e_/g g^U:5\_/p%ñ»mHgA52óUXg\xªr�dfu�] k _tbeUXxfUX[\`DUOuyMUO] k g\U:5^_epVdfp«�O`�_e_/gBmOgA5 ] k _tbeUXxfUX[\`$] k _t_�5\�O_pb8ñk¾�óAcDdfp«�X`q_e_/gO;@?�UX`e{dfuôñ&WZ_e`q�X_ep�3·dª] k ós3 k _eg�ó�dipwbeUXxfUX[\`q_�5z`q_�5�UX`Lb8ñk¾�óAc�dip:b/UXxiUO[\`�_�5z`�_�5){�ñh3·dixix£pq[\y\p�_�a£[\_eg�]5xªrk m¨oX_�]�U¤5^dip�U�3·g_ów; B gA5){£dfu:ñ&W _/`��X_/p�3·df] k óZ3 k _/gZñ&dip$beUOxiUX[\`q_�5�`q_�5){�] k _�`�_epq[\xf]�dig\�¦pR]�mH]�_W m�r k m¨oX_»mZ`q_�5�beUXxfUX[\`q_�5ºg\U65\_�3 k UXp�_&mOg^be_epR]5UX`qp¾mH`�_&mOxix�[\YO;

l"[\`�5\_e`qdfoHmH]�diUXgZmOyMU�oX_¾pq[WXZbe_/pV]5U»_eg\pq[\`�_/pV] k mL]¨{hpq]�mH`q]5dfg\�¦uÄ`�UXW mOg�r�pR]5`�[^b/]5[^`�_"dfg2[ {] k _}g\U:5^_h3·df] k ] k _ k df� k _epR]�digW5\_�P_3·dixixM_exf_eb2]·df]5pq_exªu�mOp�m�`�UhUO]�mHgA5ºbeUXxfUX[\`Vdª]5pq_exfu��X`q_e_/gºohdimm�beUXxfUX[\`�dfg\��mOb2]5diUOg){^uÄUXxfxiU�3·dig\�l3 k dib k ] k _¦`�_/W�mHdig\dfg\��g\U65\_ep03·dixfxÚÀqUXdfg�dª]5p+]�`�_e_¦ohd¹m�WZ_e`��O_mOb2]5diUOg\p�;

B uÄUX`�W mOxA5^_ep�b/`�dfY^]5dfUXg UHu)UX[\`QY\`qUX�X`�mOW g\U�3IuÄUXxfxiU�3·p�;�ItU65\_�ñzW�mOdfg�]�mOdfg\p:] k _tY�mH`�_eg�]e{`�UhUO]e{^mOgW5BbeUXxfUX[\`QoOmHxi[\_/pVdig oOmH`�d¹mHy\xi_/p˦õôå�¿ ñÏ{:åK�q��ä�¿ ñ�{\mHgA5,ö�¿�÷q{c`q_ep�YM_eb2]5dªoX_exªrk;D�_/]uø�ö4ñk¿ ñ�yM_] k _&pq_/]�UOuwg\U65\_ep�mK5qÀ�mHbe_eg�]·]5U¤ñ�; j�k _&g\U65\_ k mOp�] k `�_e_&mOb2]5dfUXg\p�= j�k _sV\`�pq]tmOb2]5dfUXgºdip�[\pq_�5]5U�b/UXxiUX[^`@ñ `�_�5OiÏmOp05\_/p�be`qdiyM_�5!mOy�U�oO_O{\] k dip·mOb2]5diUOg�dfp�_eg�mHy\xi_�5>3 k _/gù �q�4¿ ñÌá'�6å<ç�ç�úüû bý˦õôåq¿ ñ�ãþ øhö4ñk¿ ñwÿ���ñ���� ù �q�»¿9b Ë�õÚå�¿ ñ6cká,å<ç�ö�� ù �q�4¿ b^ñk¾�b ˦õôå�¿ ñ:cFcká'åKç�ö6cj�k _�p�_/beUXgA5 mOb/]�diUXgÍdfp�[\p�_�5 ]5US5\dfp�U�3·g ] k _ºY�mO`q_eg�]�UHuLñ mHgA5 ]�U `�_eb/UXxiUO[\`sñ��X`q_e_eg itmHp5\_/p�be`qdiyM_�5�mOyMU�oO_O{�] k dip·mOb2]5diUOg�dfp�_eg�mHy\xi_�5>3 k _/g

ù �<�4¿ ñ�á'åKç�ö_û b uÄUX`�_¨mHb k g\U65\_lów¾�ó þ øhö4ñk¿ ñk¾U˦õôå�¿Âóhãá2ñ6cj�k _Zx¹mOpR]&mOb/]�diUXg dfp&[^p�_�5 ]5U�W _/`��X_¤ñ!dfg�]5UB] k _�]5`q_e_�beUOg£]5mOdig^dig\�vówi:mOps5\_epqbe`�dfy�_�5 mOyMU�oX_H{] k dip·mOb2]5diUOg�dfp�_eg�mHy\xi_�5>3 k _/gó þ øhö4ñk¿ ñ©û ù �<�4¿ ñ�áD�6åKç�ç�ú×û ù �q�4¿ b^ñk¾�óAckáD�6åKç�ç�úüû ù �q�4¿�ó*áD�6åKç�ç�úüû å<�q��ä�¿ ñ���å<�<��ä�¿Âó

N _eW mO`!EÍUXg g\UO]�mL]5diUOg =.M�_![\p�_|CRY�mO`5mHW _2]5_e`qp!G�]�U p�YM_eb/dfu r ] k _�] k df`!5ImHb/]5dfUXgO; BY�mO`�mOWZ_/]5_/`¸`5mHg\�X_ep$U�oO_e`Qm�V�g\dª]5_L5^UXW�mHdigO;�v±]5p:uÄ[^g\b/]�diUXg�dfp:]5U}_/g�mOy\xf_�m"p�_2]QUOu�mOb/]�diUXg\pw]5U}yM_`�_/Y\`�_/p�_/g£]�_�5�mOp+UXg^_"Y�mO`�mOW _2]5_/`�d97/_�5ºmOb2]5dfUXgO;*?�UX`«_�P^mOWZY\xi_H{^xi_2],yM_}m�Y�mO`�mOWZ_/]5_/`g3 k UXpq_oHmOxi[^_tdfp+�^{M�"UX`V�:ic] k _eg0] k _¾Y\mO`5mOWZ_/]�_e`qd97e_�50mOb2]5dfUXgDõ ù ä�¿�?mOy\y^`�_/ohdimH]5_/pV] k _�uÄUXxixfU�3·dig\�¦p�_2]UOu�] k `q_e_&mOb2]5diUOg\p�;

õ ù ä�¿9b� =�á �ôc R Tdõ ù ä�¿9b� =Âáæ��c R Tõ ù ä�¿9b� =Âá �Kcb~Ç$gA5�UOuw`�_/W�mO`FE¦;�c

l"[\`¦Y\`qUX�X`5mHW�{� ����6{)uÄUX`}W mOdig�]�mHdig\dfg\�Bmº`�UhUO]5_�5 pqY�mOg\g\dfg\�º]5`�_/_Z] k _e`q_/uÄUX`q_ b/UXg\pqdipq]�pUOu�] k _}uÄUXxfxiU�3·dig^��] k `q_e_&mOb2]5diUOg\p+uÄUX`�_¨mHb k g\U65\_K=

Page 11: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

������� ñrb8ñ_=��k¿^¿Â��c����� åK�q��ä�¿ ñk¾UË�õÚå�¿ ñk¾�=Ï�k¿^¿��âi

ù �q�4¿ ñ�=����:å<ç�ç�ú�¾!åKç�ö��Úi� ����� � �"!#� � ó'=\�k¿^¿��âi� $ !�%&�'�)(ù �<�4¿ ñ�áD�6åKç�ç�úüûb Ë�õÚå�¿ ñJãþ øhö4ñk¿ ñ�ÿ*��ñ��+� ù �q�4¿ bý˦õôå�¿ ñ6cká'åKç�ö

� ù �<�4¿9b8ñk¾�bý˦õôåq¿ ñ6c!cká'å<ç�ö:c �wÊ ù �q�4¿ ñ�=�á|åKç�öR Tù �<�4¿ ñ�á'åKç�ö ûb-,Oó'=6óhãþ øhö4ñk¿ ñ.�©Ë¦õôå�¿�óhãá�ñ6c ��Ê ù �q�4¿ ñk¾ ù �q�4¿ b^ñk¾U˦õôå�¿ ñ6c�¾!åK�q��ä�¿ ñk¾U˦õôå�¿ ñD=�á´�6å<ç�ç�ú�¾!�6å<ç�ç�ú�¾4ñk¾ÒñR Tó þ øhö4ñk¿ ñ�ûù �<�4¿ ñ�áD�6åKç�ç�ú û ù �q�4¿ b^ñk¾�óAckáD�6åKç�ç�úüûù �<�4¿Âó*á'�6å<ç�ç�ú�û�å<�<��ä�¿ ñ/�2åK�q��ä�¿Âó � Ê åK�q��ä�¿ ñk¾UË�õÚå�¿ ñ_=Âá åK�q��ä�¿�ów¾�ó

¡$`�UX�X`�mOW0 ����

M _¾dfxixi[^pq]5`�mH]5_0¡$`qUX�X`5mHW N a j y�r�mOg�_�P^mOW Y^xi_K;�?:di�X[^`�_¾�AbÀmôc$p k U�3·p+m\m��±g\U:5^_tpRrcpR]5_/WmH]¾mOg!dfg�oOmH`�d¹mHg£]�pR]�mH]�_¤3 k _/`�_zg^U:5\_&~�dfp�] k _�`qUcUH]tUHu¸] k _&p�Y\mOg\g\dfg\� ]�`�_e_H{�pqdig\b/_�g\U65\_ZmZdfp5\U�3·gO;�TVUXg\pqd95\_/`e{wg\U�3¦{:] k mL]»g^U:5\_ ~!mHgA5 b k mOg^g\_ex�bR�X{ý�kc"u�mOdix~; vsg ] k dfp»pqbe_eg\mO`�dfU\{wg^U:5\_/p�zmHgA5���beUXxfUX[\`·] k _/W pq_exªoX_ept`�_�5!y�rº] k _/di`0V�`�pR]"mOb2]5dfUXg\pe{Ïpqdig\b/_&] k _edf`tY�mH`�_eg�]tb k mOg\g^_ex¸mHgA5Y�mO`q_eg�]¦g\U65\_O{`q_epqY�_/b/]5dªoX_/xfrX{6mH`�_p5\U�3·gO;zac[\y\pq_�a£[\_eg�]�xfrX{�g\U65\_��0beUOxiUX[\`qp"df]�p�_/xfuQ`�_�5 y£r!df]�pV�`qpq]�mOb/]�diUXg�3 k _eg dª]s5\_/]�_eb2]5p�] k mH]»df]5p¦Y�mH`�_eg�]e{:g\U65\_B�h{wdfp&b/UXxiUO[\`�_�5�`�_�5�b�?:di�X[^`�_ �Ab�y�c!c�;acdfg\be_ºg\U65\_epº��mOgA5 � k m¨oX_ºg\U b k dix85\`�_/g ] k _2r b¨mOg _exf_eb2]�] k _/W pq_exfoO_ep mOp�`�UhUO]�y�r ] k _edf`p�_/beUXgW5�mOb/]�diUXg^pZb�?:di�O[\`�_»�AbÄb�c!c8{MmOgA5!pqdig\b/_»g^U:5\_»��dip·] k _ k di� k _epR]¾[\Y�g\U65\_O{Ïg\U65\_ep&�zmHgA5��3·dfxix6ÀqUOdig�df]5p�]�`�_e_»y�r�] k _edf`�] k df`!5�mOb/]�diUXg\p�;+v±u$g\U65\_ZmZg\U�3 `q_eY�mOdf`�p/{Mdª]03·dixix�beUXxfUX[\`·df]�p�_exªu`�_�5ðb~?:df�X[\`q_z�Ab�5¦c!c8{)mOgW59p�dfg\be_zdª] k mOp"g\U0b k dix95^`�_eg!df]�3·dixix6_2oX_eg�]�[�mOxixªr!b/UXxiUO[\`tdª]5pq_exfu¸�X`�_/_egy�rBdf]�p+p�_/beUXgW59mOb2]5diUOg){\mHu ]�_e`g3 k dib k mOxix�g\U:5^_epL3·dixfxÚÀqUXdfgBdf]�pV]5`q_e_¦y�rB_�Pc_eb/[^]5dfg\��] k _/di`+] k di`F5mOb2]5diUOg\p¤b~?:df�X[\`q_&�Ab�_�c!c�;

���

Page 12: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

3,3,green

(a) Invariant state (b) Fault-span state

4 4

(a) Invariant state(a) Invariant state(a) Invariant state(a) Invariant state

4

4,4,green

3,3,green

1,4,green

(c) Fault-span statenode 5 is down

1,4,red2,4,green 2,4,red

3,4,green

1,1,green 2,4,red

1,3,green 2,3,green 1,5,green 2,5,green

after 4 and (1-2) fail-stop

3,4,red5

down node

up node

5 5

5,5,green3,5,green5,5,red

(e) Invariant stateafter 5 repairs

(d) Fault-span state down channel

up channel

4 Legend:

id,root,color

Figure 2

vsg�] k _Z`q_epR]¦UOu«] k dip¾p�_eb2]5dfUXg){3V_�Y\`qU�oX_�] k mL]1 2��� dfp}g\UXg\W mOp!E£dfg\�0u�mO[\xª]q�±]�UXxi_/`5mOg�]tUOuu�mOdfxª�spR]5UXY�u�mOdfxi[\`q_epQmOgW50`�_/Y�mOdi`qp�;�M _�y�_/�XdigZy�r b k mO`5mOb2]5_/`�d97/dig\�&] k _·u�mO[\xª]q�±p�Y�mOgZY\`q_�5\dfb¨mH]�_�ÎmOgA5º] k _&dfg�oOmH`�d¹mHg£]+Y\`�_�5\dibemH]5_lÍL;Q�_/]0Î|á�X`�mOY k UOu:] k _¦Y�mO`q_eg�]�`�_eximH]5dfUXg0dfptmzuÄUX`q_epR]tUHuw]�`�_e_/p

û´b-,Wñ�=.ñ�dip�[^Y Þb ù �q�4¿ ñÌá'åKç�ö Þ b ˦õôå�¿ ñ�ãþ øhö4ñk¿ ñwÿ���ñ��3� ù �<�4¿9b ˦õôå�¿ ñ:cKá,å<ç�ö�� ù �q�»¿9b8ñk¾�b ˦õôå�¿ ñ6cFcká,å<ç�ö6c!c

û bý˦õôå�¿ ñ�á2ñ Þ å<�q��ä�¿ ñ�á�ñ6cû bý˦õôå�¿ ñJãá2ñ Þ å<�q��ä�¿ ñ54lñ6cû bý˦õôå�¿ ñ þ ø�ö4ñk¿ ñ Þ b�å<�<��ä�¿ ñ/6_å<�q��ä�¿9b ˦õôå�¿ ñ:c7� ù �q�4¿ bý˦õôåq¿ ñ6cká'åKç�ö8� ù �<�4¿9b8ñk¾�bý˦õôåq¿ ñ6c!cká'å<ç�ö:cFc!c

û´b-,,ñk¾�ó'=|b8ñk¾�óWc�dfp�[\Y û ù �<�4¿9b8ñk¾�óWcká,å<ç�ö Þbý˦õôå�¿ ñ�ávóSûob ù �<�4¿ ñ�á'åKç�ö9� åK�q��ä�¿ ñ/4�å<�<��ä�¿ÂóAc!c

� bý˦õôå�¿�ó*á�ñ�ûob ù �<�4¿Âó*á,å<ç�ö:� å<�<��ä�¿�ó;42å<�<��ä�¿ ñ6cFc!c

�X�

Page 13: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

B gW5�xf_/]JÍzáÎ

û´b-,Wñ�=.ñ�dip�[^Y Þb ù �q�4¿ ñÌá'åKç�ö < b ˦õôå�¿ ñJãþ ø�ö4ñk¿ ñ�ÿ���ñ��=� ù �<�4¿9b ˦õôå�¿ ñ:cKá,å<ç�ö�� ù �q�»¿9b8ñk¾�b ˦õôå�¿ ñ6cFcká,å<ç�ö6c!c

û ù �q�»¿ ñÌá'�6å<ç�ç�úû b>,Oó,=6óhãþ øhö4ñk¿ ñ?� å<�q��ä�¿ ñpá´å<�q��ä�¿ÂóAc!c

@BA �C� � � � DFE ��G!�6�IHv���U�K�JGD�LKM ����=NOH GQPRG�ÍSH��UTWVq�IXu�YH G[Z\PF�Q] Hz�LKZ�&H G2]W�\PRG����^PIGQT^�K��_U�q�_9�Z�7PH���q�JG`V2�J]W�K��� _f�aZ2��PIGIGcbd � �e�'f`g B ]Q_emOb k pR]�mH]�_L3 k _e`q_hÍ k UXx85\pe{kÎ k UXx85\pQmOgA5){X] k _e`q_/uÄUX`q_O{�] k _��X`5mOY k UHu�] k _�Y�mO`q_eg�]`�_/x¹mH]�diUXg�dfp&mºuÄUX`q_epR]�UOuD]5`q_e_/p�;_M _ p k U�3 ] k mH]¦] k dfp¦uÄUO`�_epR]&beUXg\pqdipR]5p&UOu+_�P\mHb/]5xªr UXg\_�]5`q_e_<=B ]�_emOb k pq]�mL]5_�3 k _/`�_¤Í k UXx85\pe{^mOxixMg\U65\_ep+mO`�_"b/UXxiUO[\`�_�50�X`�_/_eg){ k m¨oX_¦m�Y�mH`�_eg�]�] k mH]+dfp+[\Y){mOgA5 k m�oO_}] k _}p�mOW _¾`�UhUO]+oHmOxi[^_K;@t�UO`�_eU�oO_e`e{ÏmHxix�b k mOg\g\_/xip·mO`q_"beUXxfUX[\`q_�5B�X`q_e_eg ;Dv±]VuÄUXxixfU�3·p] k mH]«] k _e`q_¾dfpD_�P^mOb/]�xfrZUXg\_�g\U65\_Lñzp�mH]5dfpqu rhdig\�¤å<�<��ä�¿ ñÌá�ñjû ˦õôå�¿ ñÌá�ñ�mOgA5){ k _eg^be_O{^_�P^mOb/]�xfrUXg\_}]�`�_e_<; h

i � �+�+�kj Íl_9�Z�nm�op]��U_f���u�LK� ����)b

i � �+�+�kq Îr_9�Z�QT9���#G`V7_f�s ����)b

@BA �C� � � � tvuIw T9���QxaPIGJy Îr_9�p�QT9���#G`Vzx:�'VaGQP�K��\_YT|{U���4�I]}K��\_YT|xaPIG��Z�K�'VzPIGJ]W�\_YPH�cb

@BA �C� � � � ~�uIw �q� �\GQP�ZaG�� �IGJy �¦�U�\P���_f�aZK�PH�U�ü�K� �Z���U�K�LG�NOH GQPRGgÎSH��UTWVq�IX�GQ�\GQP��_���U��]'xa{�U�K��_U�q�z�LK� �����PRG!�6�IH G��l�2���U�K�LG[NOH GQPRGJÍ?H��UTWVq�cbd � �e�'f��`(c���"! $ A�� g l"[\`&Y\`�UhUOu+dfp»dfg ] k `�_/_�pR]�mO�X_/p�=p?wdi`�pR]¨{%3V_ p k U�3 ] k mH]»pq]�mH`q]5dfg\�ºuÄ`�UXWmOg�r0pR]�mH]�_h3 k _e`q_hÎ k UXx95\p/{\_/oO_e`RrBbeUXWZY\[^]5mH]5dfUXg0UOu� �����`�_emOb k _ep�mzpR]�mH]�_h3 k _e`q_B� k UXx85\pe{��� bfÎeû b>,WñQ=�ñ�dfp¾[\Y Þ b ù �q�4¿ ñ½á�å<ç�ö0< b ˦õôå�¿ ñlãþ øhö4ñk¿ ñOÿ[��ñ��l� ù �<�4¿9b ˦õôå�¿ ñ6cAáå<ç�ö9� ù �q�»¿9b8ñk¾�b ˦õôå�¿ ñ6cFcká,å<ç�ö6c!c�;$ac_/beUXgA5�{Ú3«_�p k U�3 ] k mL]$pq]5mO`q]�dig\�¾uÄ`qUXWæmOg�rzpq]5mH]5_L3 k _e`�_��k UXx85\pe{�_2oX_/`qrºbeUOW Y\[c]�mH]�diUXgBUOu5 ����!`q_¨mOb k _/p¾m�pq]5mH]5_�3 k _/`�_B� k UXx95^pe{'��� bJ�ðûzb-,Wñ�=�ñdip}[^YüÞ ù �q�4¿ ñvá©�6åKç�ç�úOc!c�;\?:dig�mHxixfrO{w3«_�p k U�3 ] k mH]¦pR]�mO`R]5dig^�ºuÄ`qUXW mHg£r!pq]5mH]5_p3 k _/`�_7�k UXx85\pe{^_/oX_/`qr�beUOW Y\[c]�mH]�diUXgBUOu/ ����!`q_¨mOb k _eptmZpR]�mH]�_s3 k _e`�_lÍ k UXx95\p�; h

M _0WZ_¨mOpq[\`�_�] k _ ]�diWZ_�b/UXW Y^xi_�Pcdª]sr UOu·beUXg�oO_e`��O_eg\b/_º]�USÍ(dig ]�_e`qW pzUHu·`�UX[\gW5\p,R��qTU;B `qUX[\gA5�diptm�WZdig\dfW�mOxÀ{^g\UOg\_eWZY^]sr�p�_�ah[^_eg\b/_�UOu$Y\`qUX�X`5mHW.pq]5_/Y\p�3 k _/`�_/dig!uÄUX`�_¨mHb k g\U:5^_

���

Page 14: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

] k _e`�_«_�PcdipR]5pwmtpR]5_eYl3 k _e`q_«] k _«g\U65\_«_edf] k _e`6_�P^_/be[^]�_epQmOg�mOb/]�diUXg&UX` k mOp�g\U¾mOb/]�diUXg\p�_eg\mOy\xi_�5yM_/uÄUX`q_&UO`·mHu ]5_/`+] k _¦pq]�_eYO;

ah]5mO�X_9�B`q_�a£[\df`�_ep�mL]�W UOpq]�} `qUX[\gA5^p�i+pR]�mO�X_B�!`�_�a£[\df`�_/p�mH]�WZUXpq]�} `�UX[\gW5\p�i�mHgA5pq]5mO�X_��!`�_�ah[^di`�_/pzmH]�W UOpq]z�K} �'�!`�UO[\gA5\p/{�3 k _e`q_'} dfp»] k _�g£[\WzyM_e`»UOu·[\Y g^U:5\_/p�;�v±]uÄUXxfxiU�3·pV] k mH]·] k _}]5dfW _¾beUXWZY\xi_�Pcdf]sr0UHu�ÐsÍ�Î(dfp0{Db�}dcV`�UO[\gA5\p�;

M _¾`q_/uÄ_e`«] k _t`�_¨m<5\_e`V]�U'R����qTMuÄUX`«uÄUO`�W mOx�Y\`�UhUOuÄp«UOu6mOxfxMxf_eWZW�mHpVmOgW5�] k _/UX`�_/W p«digZ] k dfpY�mOYM_e`�;

� é ­\1�$'&�­\1�$.1�$dê � � $.1�+.1�(*ª�/0&�1�)2$d­\«|ë 1�$dê

vsgz] k dip¸pq_eb/]�diUXg�{k3V_�_/W Y\xfU�r&] k _�p�_/beUXgW5ZUHuM] k _V]43«Us5\_epqdi�Xg�WZ_/] k U:5^p�5\dipqbe[\pqp�_�5 dfg�ac_eb2]5dfUXg�0]5U�5\_/`�dªoX_ºm9g\UXg^W�mOpFE£dig\�9u�mO[^xf]q�ô]5UXxf_e`�mOg�]�Y\`qUX�X`�mOW uÄUO`zW�mHdig�]�mOdfg\dig^�!m�[\g\d85\di`q_eb2]5diUOg�mOx`�dfg\�A; N _/b¨mOxfxQ] k mH]&dig ] k dip&W _2] k U65){%3V_ p k U�3 ] k mH]&`�_e�XmO`!5\xf_epqp�UOu«] k _Zpq]5mO`q]�dig\��pq]5mH]5_ZUOu] k _zY\`�UO�X`5mOW�{Mp�[\y\pq_�a£[\_/g£]&b/UXW Y^[^]�mH]�diUXg�UOu$] k _zY\`�UO�X`5mOW,b/UXg�oX_e`q�X_ep�3·dª] k dfg9m�yMUX[\gA5^_�5g£[\WzyM_e`wUOu\pR]5_eY^p:]5U¾m�pR]�mH]�_Vdigs3 k dfb k ] k _½5\_epqdi`q_�5�pR]5`q[\b/]�[\`�_H{�dig¦] k dfpwbemOp�_Vmt[\g\d85\di`q_eb2]5diUOg�mOx`�dfg\�\{\dfp�_epR]�mOy\xfdip k _�5O;

j U WZUO]�dfoHmH]5_tUX[\`·Y\`qUX�X`5mHW×5\_/`�dfoHmH]�diUXg�{:3«_¤V�`qpq]��XdªoX_¦m�beUXg^pq]5`q[\b/]�dfoO_»Y\`qUcUHu:UOui � �+�+�k�lE x6� _�V\_YPRG�����_U�q���\T�PQ_f�aZ�GQ�z�QG`V"V\_f�aZ'�LK*T>G��aZK�YHv�K�/�_�����w�Ab~}ð�Z��cZ�K�'V�V\_YT^�K��_U�q��K�5�_�����;�>�!�K���QGBGQ�z�QG`V"VaG`V7_f���K�S�\Pp�c_f��PF�\P����cx:�u���q���eG����LG`VBZ\P!�Q] H�bd � �e�'f =��¦dªoX_eg�mOg�rBb/UXg\g\_/b/]5_�5!�X`�mOY k {\mZ`qUcUO]�_�5ºp�Y\mOg\g\dfg\��]5`�_/_¦b¨mOg�y�_¦_/Wzy�_�5A5\_�5�dfg�dª]�;M _�p k U�3 y�r�pq]�`�[\b2]5[\`�mOx�digA5\[^b/]5dfUXg!UOg�] k _ k _/di� k ]��!UOu¸] k _�`�UhUO]�_�5!pqY�mOg\g^dig\�Z]5`�_/_O{Ï] k mL]m![\g^d95\df`�_eb2]5dfUXg�mOxQ`�dfg\�9bemOg y�_�_eWzyM_�5A5^_�5Ídig�] k _0`qUcUO]�_�5 pqY�mOg\g^dig\�9]�`�_e_�p�[\b k ] k mH]z] k _uÄUXxfxiU�3·dig\�»]43VUZY\`�UOY�_/`q]5df_ep�mO`q_}p5mH]�dipFV\_�5O;�k;·vsg�] k _¾`qdig\�»_eWzyM_�5W5\dig\�^{h] k _¾pq[\beb/_ep�pqUX`�UOu)] k _¾`qUcUH]VdfpVm�b k dix95 UOu)] k _¾`qUcUO]e{^mHgA5�] k _`qUcUO]·dfp+] k _¦pq[\beb/_ep�pqUX`¾UHu¸m��X`�mOgA5\b k dfx95ºUOu�] k _¦`qUcUO]�;

�:; j�k _Zxi_/g\�O] k UOu«] k _�`qdig\��dip¦mH]&WZUXpq]��Ab�} �º��c}mOgA5 ] k _�5\dfx¹mH]�diUXg�UHuV] k _Z`qdig\��dip¦mL]WZUXpq]��:;

x+mOpq_�T+mOp�_Sb���á��kc2= j�k _0]5`�_/_BbeUXg^p�dipR]5p�UOu�m9pqdig\�Oxi_�g^U:5\_H{ k _eg\b/_�m9p�_exªu¹�sxfUcUXY UXg ] k _g\U65\_}dip·m�[\g^d95\df`�_eb2]5dfUXg�mOxM`�dfg\��_eWzyM_�5A5^dig\�z] k mH]·p5mL]5dipnV�_ep�] k _¦Y\`�UXYM_e`R]5df_ep}�/�F�:;0b j U�oX_e`qdfu rY\`qUXY�_/`q]sr��O{A3V_¦xi_2]�mZxf_¨mHu�g\U65\_¦yM_&dª]5p�U�3·g�b k dix85�mHgA5){ k _/g\be_H{Ïdf]5p�U�3·g��X`5mOgW5\b k dix85O;Âc

���

Page 15: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

vsgA5\[^b/]5dfUXg ah]5_/Y�b��.4,�ôc_=,?�`�UXW ] k _BdfgA5\[\b2]5dfUXg k rhYMUO] k _ep�dfpe{QuÄUX`�_¨mHb k b k dfx95 ù UOu�] k _`�UhUO]¤åºUOuV] k _Zp�Y�mOg^g\dig\��]5`q_e_O{:m�`qdig\�>å<÷~úw��¿ ù b¨mOg y�_Z_eWzyM_�5W5\_�5 dfg ] k _ pq[\y^]�`�_e_ `�UhUO]5_�5mH] ù pq[\b k ] k mH]�] k _¦Y\`�UXYM_e`R]5df_ep¦�/�R�zmH`�_}p5mL]5dipnV�_�5 ;Dvsg�Y�mO`R]5dfbe[\ximO`e{huÄ`�UXW Y\`�UXYM_e`R]sr��X{^] k _e`q__�Pcdfpq]5pDm¦g\U65\_�� ù ¿ ù ] k mH]QdipQm<5qÀ�mObe_/g�]D]�U ù dig�å<÷~úw��¿ ù mOgA5 mH]Dm�5\dipR]�mOg^be_·UOu)6 �·uÄ`qUXW ù ;�M _beUOg\pq]�`�[\b2]}g\_�Ph]&mZ`�dig^�0_eWzyM_�5W5\dig\� dig!] k _�]�`�_e_»`�UhUO]5_�5�mH]�åZuÄ`qUXW.] k _z`qdig\� _eWzyM_�5W5\dig\�OpdigB] k _¦p�[\y^]�`�_/_ep�`�UhUO]5_�5�mL]�] k _¦b k dix85\`�_/gºUOu�å6;

1

c

fc. fc.1c

1c c

c

r

cc2

fc.

2

c

fc.1c fc.c fc.c2

2

1c

r

Figure 3

(ii) (ii)(ii)

(i)

(iii) (iii)

c =fc.r1

(iv)

N

N

N

N

(a) Induction Hypothesis : Ring embeddings for subtrees rooted at c , c , ... , c

(b) Induction Step : Ring embedding for tree rooted at rNote the reversal of subtree embeddings

N2

TVUXg^p�d95^_e`«] k _¾b k dix95^`�_eg UOuå¦dig p�UXWZ_0VWPc_�50]5UH]�mOxÏUX`F5\_e` ù#� ¾ ùQ� ¾�¿8¿^¿ ùQ  {63 k _/`�_ ù¡� á¢� ù ¿�åb~?wdi�X[\`q_z�Xmkc�;_b�dfc¾TVUXg\g\_/b/]¤å ]�U ù#� ;Db�dfdfc�vsg£oO_e`R]»] k _�p�[\b/be_/p�p�UO`»`q_ex¹mL]5diUOg!UOuD_¨mHb k åq÷Uú��w¿ ù¤£ {��6�ñ¥� }`;vb�dfdid c�¦"_/xi_/]�_zuÄ`�UXW1_¨mOb k åq÷Uúw��¿ ù§£ {Q��6�ñ¥6�} {] k _�_�5^�X_�uÄ`�UXW¨� ù ¿ ù¤£ ]5U ù¤£ {mOgA5�beUOg\g\_eb2]*� ù ¿ ù§£ ]5U ù§£ª©�� ;hbÄdfoWc¦"_exf_/]5_}uÄ`qUXW×åq÷Uú��w¿ ùQ  ] k _&_�5\�O_¦uÄ`qUXWv� ù ¿ ùp  ]�U ùQ  {ÏmHgA5beUOg\g\_eb2]M� ù ¿ ùQ  ]�UDå:; j�k _�`�_epq[\xf]�dig\� pq]�`�[\b2]5[\`q_Qb�?:di�O[\`�_»�Oy¦ctdfp"m0`qdig\�Z] k mH]"p5mH]�dipFV\_ep"] k _Y\`qUXY�_/`q]�di_ep}�2�R�:; h

�¨~

Page 16: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

vsg�mOb/beUX`F5�mOg\b/_g3·df] k ] k _«beUXg^pq]5`q[\b/]�diUXg�mHy�U�oX_H{k3V_�Y^`�UXYMUXp�_D]5U�5\_/`�dªoX_�m¾Y^`�UX�X`�mOW ] k mL]beUOg\p�dfpq]5p&UOu«]43VU�x¹m¨rX_/`�p�= j�k _�V\`�pq]»x¹m¨rO_e`¦UOu+UO[\`»Y^`�UX�X`�mOW W mOdig�]5mOdig\p/{dig m�g^UXg\W mOp!E£dig^�u�mO[\xª]q�ô]5UXxf_e`5mHg£]:u�mOp k dfUXg){£m¦`�UhUO]5_�5�p�Y�mOg^g\dig\�¦]5`q_e_<; j�k _tpq_eb/UXgA5�xim¨rX_e`QUOu�UX[\`QY\`qUX�X`5mHW [\pq_ep] k dip�`�UhUO]5_�5 pqY�mOg\g^dig\� ]5`�_/_�]�U W mOdfg£]5mOdig�{Ddfg m pq]5mOy\dfxid97/dig\�9u�mH[\xf]R�±]5UOxi_e`�mOg�]zu�mOp k diUXg�{«] k _5\_/p�di`q_�5�[\g\d85\di`q_eb/]�diUXg\mOx�`qdig\�A;

M _BW�m¨r�diWZY\xi_/W _/g£]»] k _DV\`�pq]Zxim�rO_e`�dfg ]5_e`qW p�UHu"mOg�r�g\UXg\W mOp!E£dfg\�9u�mO[\xª]q�±]�UXxi_/`5mOg�]Y\`qUX�X`5mHW�uÄUX`¦W�mHdig�]�mOdfg\dig^�Bm�`qUcUO]�_�5 p�Y�mHg\g\dig^��]�`�_e_H{:_<; �A;ª{Ì¡Q`qUX�X`�mOW� ���� UOu�ac_eb2]5diUOg��W;?�UX`BUX[\`BY^[\`�YMUXp�_/pe{h3«_ WZ_e`q_exªrImOpqp�[\WZ_�] k mH]º] k _�uÄUXxixfU�3·dfg\��oHmO`qd¹mOy\xf_epD5^_ep�b/`�dfy\dig\�Í] k _`�UhUO]�_�5ºp�Y�mHg\g\dig^�Z]�`�_e_&mO`q_¦m¨oOmHdix¹mHy\xi_�]5U�] k _¦p�_/beUXgW5�xim�rO_e`·UOuw_¨mOb k g\U65\_�ñ¦;

à ˦õôå�¿ ñÏ{�5^_eg\UO]�dig\��] k _¦Y�mO`�_/g�]tg^U:5\_¦UOu ñ.bý˦õôåq¿ ñpáðñ�dfuwñ�dfp+] k _¦`�UhUO]�g^U:5\_�c�;à � ù ¿ ñÏ{%5\_/g\UO]�dig\��`�_/p�YM_eb/]�dfoO_exfr�] k _pV�`�pR]�g^U:5\_�dfg pqUXWZ_�V:P^_�5 ]�UO]�mOx$UO`!5\_/`�dig^��UHuV] k _b k dfx95\`q_egºg\U65\_¦UOu ñdb«� ù ¿ ñpáeñ dfuwñ�dip·m�xf_¨mHuHc�;

à ú­¬ô¿ ñ�{w5^_eg\UO]�dig\� `�_/p�YM_eb/]�dfoO_exfr�] k _�g\_�Pc]¾p�dfy\xidfg\� UHu%ñ0dig�] k _¤VWPc_�59]5UH]�mOx6UX`F5\_e`qdig\�ZUOu] k _¦b k dix85\`�_/g�g^U:5\_¦UOu�˦õôå�¿ ñdb�ú�¬k¿ ñpáeñ dfuwñ�dip+] k _¦x¹mOpR]·b k dix85BUOu�˦õôåq¿ ñ6c�;

à ç¡®6ç�ú�¿ ñ�{Xm·y�UhUXxf_¨mOgs5\_/g\UO]5dfg\�03 k _/] k _e`wñ"dip�mH]wmOg&_/oO_eg\5\dfpq]5mOg\be_QuÄ`�UOW ] k _D`�UhUO]�g\U65\_K;b j U�p�_/_&] k mH]�ç¡®6ç�ú�¿ ñ�dfp�diWZY\xi_/W _/g£]�_�5D3·dª] k UX[c]�mK5A5\dfg\��]5U�] k _}]�diWZ_"beUXWZY\xf_�Pcdf]sr UOu] k _uV�`�pR]Vxim�rO_e`QY\`qUX�X`5mHW�{XUOy\p�_/`qoX_�] k mL]«dª]5pQmOb2]5dfUXg\p$b¨mHg�yM_tmH[\�XWZ_eg�]5_�5Z]�U&W mOdfg£]5mOdigm�oHmO`qd¹mOy\xf_Zç¡®6ç�úÌ¿ ñ�; j�k _z_2oX_eg oHmOxi[^_�UOuÌñºdipt]�`�[\_H{)dfuñºdip¾m0`�UhUO]"g^U:5\_H{mOgA5�dfp¾] k _g\_/��mH]�diUXgBUOuw] k _¦_2oX_eg�oHmOxi[\_}UHuw˦õôå�¿ ñÏ{�dªuwñ�dip�g\UH]�mZ`qUcUO]+g\U:5^_K;Âc

M _9g\U�3ì5\_epqbe`�dfy�_�] k _9pq_eb/UXgA5'x¹m¨rX_/`�;ã�_/]B[^p0`�_/Y\`�_/p�_eg�]º] k _9[\g\d85\di`q_eb/]�diUXg\mOx·`�dig^�dig ]5_e`qW p»UOu�m�Cqpq[\beb/_epqp�UX`FG `q_eximH]5dfUXgOi:] k _0p�_/beUXgW5 x¹m¨rX_/`zdig _¨mOb k g\U65\_\ñ�W mOdig�]5mOdig\p¦] k _digW5\_�P UHu«] k _ b/[\`�`q_eg�]»p�[\b/be_epqp�UX`»UOu�ñ!dig�] k _Z`qdig\�W;�?ÏUOxixiU�3·dfg\�0pq]�_eYÁb�dfc¾UHu«] k _�_�PcdipR]5_eg^be_Y\`qUcUOu:mOyMU�oX_O{A3«_¦b k UhUXp�_}] k _&pq[\beb/_epqp�UX`�uÄUX`+] k _¦`qUcUO]LåzUOu�] k _¦p�Y\mOg\g\dfg\��]5`�_/_}]5U�y�_[� ù ¿�å:;?�UXxixfU�3·dig\��pR]5_eY bÄdid c�UOu"] k _!_�Pcdfpq]5_/g\be_!Y\`�UhUOu}mHy�U�oX_H{L3V_!b k UcUOp�_�] k _!pq[\beb/_epqp�UX`0uÄUX`�] k _g\UXgh�s`�UhUO]»g\U65\_ep�ñ UOu+] k _0pqY�mOg\g\dfg\�9]5`q_e_H{$mOp�uÄUXxfxiU�3·p�;9acdig^be_ ] k _0pq[\beb/_ep�pqUX`�`�_/x¹mH]�diUXg UOu] k _»`qdig\�Z_eWzyM_�5W5\dig\�Op�UHuQmOxix�p�[\y^]�`�_/_ep"dfp�dfgA5\[\b2]5dªoX_exªrBdig�oO_e`q]�_�59dfg�pR]5_/Yyb�dfdfc2{:3V_&beUXg^bexi[W5\_] k mH]¾] k _ZV�g�mHxwoHmOxi[^_�UOu$] k _zp�[^bebe_/p�pqUX`¦UOuñ'5\_eYM_egA5^p&pqUXxi_/xfrºUXgd3 k _/] k _e`"] k _\5\_eYc] k UOuñdigB] k _¦p�Y�mOg^g\dig\��]�`�_e_¦dfp�U:5A5ºUX`�_2oX_/gO=«dªuOñZdip·mH]�mHg�U65A5,5\_eYc] k {\] k _egº] k _¦pq[\beb/_ep�pqUX`¾UHuOñdip05\_2]5_/`�WZdig\_�5�y�r�pq]�_eY\p\b�didfdfcQUX`lb�dfoWc�i�mHgA5�dªuñ�dfp�mH]tmOg!_2oX_egQ5\_eY^] k {Ï] k _/g�] k _»pq[\beb/_ep�pqUX`UOu ñ�dipu5^_/]5_/`�WZdig\_�5ºy£rB] k _¦dig�oX_/`�pq_»UOuwpq]�_eY\pZb�dfdid cQUX`lbÄdfoWc�;

��m

Page 17: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

t�UO`�_¾pqY�_/bed^V�b¨mOxfxfrO{c�XdªoX_/g'ç¡®6ç�ú�¿ ñÏ{63V_¾b¨mOg0[^g\d9a£[\_/xfr25\_/]�_e`qW dfg\_�] k _¾pq[\beb/_epqp�UX`2¬k¿ ñ�uÄUO`_¨mHb k g\U65\_�ñ�dfg�UOg\_}pq]�_eY){MmOp�uÄUXxfxiU�3·p�=bÀmkc2ñZdip·mH]�U65A5,5\_eY^] k mHgA5vú­¬k¿ ñ�ãá2ñv=¸uÄ`�UXW�pR]5_/YjbÄdidid c2{�¬k¿ b�� ù ¿ ñ6cká'ú�¬k¿ ñ�;b�y�c2ñ�dip¦mH]¦_2oX_eg`5\_eYc] k mHgA5�ú�¬k¿ ñ�ãádñz="uÄ`qUXW�pR]5_/Y�b�dfdid c�mOgW5 ] k _�dig�oX_/`�p�dfUXg mO`��O[\W _/g�]

W mK5\_¦mOyMU�oX_H{'¬ô¿9b�ú­¬k¿ ñ6cká¯� ù ¿ ñ�;b�b�c2ñZdip·mH]�U65A5,5\_eY^] k mHgA5vú­¬k¿ ñÌá2ñv=¸uÄ`�UXW�pR]5_/YjbÄdfoWc2{�¬k¿9b«� ù ¿ ñ:cKáp˦õôå�¿ ñ¦;b�5�c2ñ�dip&mH]¦_/oO_eg`5\_eY^] k mOgW5Sú­¬k¿ ñ�á.ñ`=}uÄ`�UOW�pq]�_eYÁb�dfoWc"mOgW5 ] k _�dig�oX_/`�pqdiUXg mO`��O[\W _/g�]

W mK5\_¦mOyMU�oX_H{'¬ô¿9b Ë�õÚå�¿ ñ6cká°� ù ¿ ñ�;

l"[\`�pR]�mOy\dfxid87edig^��u�mO[\xª]q�±]�UXxi_/`5mOg�]VY\`�UX�O`5mOW�{^±­ ¾{\uÄUO`+] k _¦p�_/beUXgW5!x¹m¨rO_e`�dip+] k _e`q_/uÄUX`q_K=

������� ñ�b8ñ�=��¤¿^¿Ú��c�³²7���a� ����� ˦õôå�¿ ñk¾I� ù ¿ ñk¾Hú­¬ô¿ ñD=��k¿^¿�� i

ç¡®6ç�ú�¿ ñD=�´h���UT>G!�K��i( A ��� �a� ����� ¬k¿ ñ�=��k¿8¿Â�âi

� $ !�%&�'�)(ç¡®6ç�ú�¿ ñ ûÔ˦õôå�¿ ñ�á2ñ ûr¬ô¿ ñ�ãá°� ù ¿ ñ ��Ê ¬ô¿ ñ�=Âá¢� ù ¿ ñ

R T¶µ*ç¡®6ç�ú�¿ ñ ûoú�¬k¿ ñ�á�ñ ûr¬ô¿9b«� ù ¿ ñ6c ãápË�õÚå�¿ ñ ��Ê ¬ô¿9b«� ù ¿ ñ6cg=�áðË�õÚå�¿ ñR T ç¡®6ç�ú�¿ ñ ûoú�¬k¿ ñ�á�ñ ûr¬ô¿9b Ë�õÚå�¿ ñ6c ãá°� ù ¿ ñ ��Ê ¬ô¿9b Ë�õÚå�¿ ñ6cu=Âá.� ù ¿ ñR T¶µ*ç¡®6ç�ú�¿ ñ ûoú�¬k¿ ñ�ãá�ñ ûr¬ô¿9b«� ù ¿ ñ6c ãá,ú­¬k¿ ñ ��Ê ¬ô¿9b«� ù ¿ ñ6cg=�á ú­¬k¿ ñR T ç¡®6ç�ú�¿ ñ ûoú�¬k¿ ñ�ãá�ñ ûr¬ô¿9b�ú­¬k¿ ñ6c ãá¯� ù ¿ ñ ��Ê ¬ô¿9b�ú­¬k¿ ñ6cL=�á?� ù ¿ ñ

¡$`�UX�X`�mOW ±­

M _9dixfxi[\pR]5`�mH]5_>¡$`�UX�O`5mOW ±­ ×3·dª] k ] k _9_�P^mOWZY\xf_!UOus?wdi�X[\`q_��:; �_/]B[\p�UX`!5\_/`�] k _b k dfx95\`q_eg�UOuDg\U65\_ep¦pqY�mH]5dimOxixªrBuÄ`�UXW?xi_2u ]"]5UB`qdi� k ]�;»vsgS?:df�X[\`�_��AbÀmôc8{�] k _�UXg\xfr�b k dfx959UOuD] k _`�UhUO]Dg\U65\_O{h~\{hdipDg\U65\_"�6i k _/g\be_*¬ô¿Õ~lá(�&y�r�] k _JV�`qpq]VmOb/]�diUXgO; j�k _¾b k dfx95\`q_eg UOug\U65\_¾�»mO`q_�¦mOgA5º�c{^g\U65\_z�}dfp+b k dix85\xi_/p�p/{\mOgA5¯µ*ç¡®6ç�ú�¿ý� k UXx85\p�i k _eg\b/_[¬k¿f��á m�y�r�] k _"pq_ebeUOgA5!mHb/]5dfUXgO;ItU65\_»� p�mH]5dfpFV�_/phç¡®6ç�ú�¿ �0mOgA5 k mOp�g\U0pqdiy\xfdig\��]5U�] k _�`�df� k ]�i k _/g\be_H{�¬k¿Â�pá �Zy£rº] k _»] k di`F5mOb2]5diUOgO;�?wdig�mOxfxfrO{Lg^U:5\_t�+dip�b k dfx95\xf_ep�p:mOgA5zg^U:5\_V�tdfp:df]�pwg^_�Ph]$p�dfy\xidfg\�Ai k _eg\b/_n¬k¿ý�¤áæ�Vy£r&] k _

���

Page 18: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

V\u ] k mOb2]5diUOgO; j�k [\pe{ ¡$`�UX�X`�mOW·��Ðærhdi_/x95\p·] k _&[\g\d85\di`q_eb2]5diUOg�mOx`�dfg\�Qb�~A¾8�6¾��W¾¨��c�;V�d8EO_�3·dfp�_H{digv?:df�X[\`�_»�AbÄ_�c8{e¬k¿ÂmZá �W¾�¬k¿ �Zá �:¾I¬ô¿ý�Zá �K¾�mHgA5:¬k¿ª��á�mZmHgA5){�] k [\p/{ ¡$`�UO�X`5mOW·��Ðærhdf_ex95^p] k _&[^g\d95\df`�_/b/]5dfUXg�mOx�`�dfg\�>bUm:¾5�W¾8�:¾¨��c�;

vsg ] k _B`�_/pq]�UOu·] k dip»p�_eb2]5dfUXg){�3«_BY\`�U�oX_0] k mH]8±­ dipzg\UOg\W�mHp!E£dig\��u�mO[\xf]R�±]�UXxi_/`5mOg�]&UOuu�mOdfxª�spR]5UXYBu�mOdfxi[\`q_ep·mOgW5!`�_/Y�mOdf`�p�;LM _&y�_/�Xdig�y�r�b k mO`5mOb2]5_/`�d97/dig\��] k _�dig�oHmO`qd¹mOg�]·Y\`q_�5\dfb¨mH]�_\ÍmOgA5ºu�mO[\xª]q�±p�Y�mOgBY^`�_�5^dib¨mL]5_�Τ;

�_/]\Í yM_Z] k _ Y^`�_�5^dib¨mL]5_25\_eg\UH]5dig^�!mOxfx$pq]5mH]5_/pl3 k _/`�_�g^U!mOb2]5dfUXg UHu�Y\`�UO�X`5mOW ±� ãdfp_eg\mOy\xi_�5){6mOgA5�xf_/]hÎæyM_z] k _�Y\`q_�5\dfb¨mH]�_Zä»åqæwçk;lItUH]5_z] k mH]¨{)y�rQ5\_�V�g^df]5dfUXg){%ÍIdip"m_VWPcY�UXdfg�]UOuB±� 'mOgA5,Î(dip�b/xiUXpq_�5�dig�±­ mOpL3«_exix6mHp·u�mHdixª�±pq]�UXY�u�mOdfxi[\`q_ep·mOgA5º`q_eY�mOdf`�p�;

i � �+�+�¹¸.E �nG!�6�IHD���U�K�JG\�LKº±­ »NOH GQPRGJÍ?H��UTWVq�IX�K��UPBG!�6�IH,� �cVaG�ñ�X@�YH GQPIG[_9�����U��Gs� �cVaGó u ]������Q_��cT|�¼_�VaG�����_U�!�\TO�»�Jñ\yp�Qx��IH,�YHW�K��¬k¿ ñÌá>ó­b

i � �+�+�k½lE ��G!�6�IH����Ò�K�JGl�LK7±­ lNOH GQPRGL;H��UTWVq�IXaK��UP*G!�6�IH�x#]Q� �cVaG�ñ�X��&H GQPRG�_9�0���U��G�x#]� �cVaGJó u ]������Q_��cT|�¼_�VaG�����_U�!�\TO�4�Jñ¿yp�Qx��IH>�YHW�K��¬k¿Âó*á2ñ'b

�_eWZW mOpL�»mOgA5º��dfW Y\xªrz] k mH]�mH]V_¨mOb k pR]�mH]�_�3 k _/`�_¤Í k UXx85\pD] k _"dfgc�45\_/�X`�_/_"mOgW5BUX[^]q�5\_/�X`�_/_�UOu$_emOb k g\U65\_�ñ0digº] k _»�X`5mOY k UOu¸] k _�pq[\beb/_epqp�UX`}`q_ex¹mL]5diUOg�dfp»�K;·|t_eg^be_O{M] k _»�X`5mHY kUOu�] k _¦pq[\beb/_ep�pqUX`¾`q_eximH]5dfUXgBdip·m�beUOxixi_/b/]�diUXgBUOuwg\U65\_�5\dfp�ÀqUXdfg£]·`qdig\�Op�;�M _&bemOg�g\U�3(Y\`qU�oO_

@BA �C� � � � ÀlE �;G!�6�IH2���Ò�K�JGZ�LK�±� ÁNOH GQPRGuÍFH��UTWVq�IX��&H GnZ\P!�Q] H>�LKh�YH G��Qx¦���IG������UP2PIGQT^�K��_U�q�_9�Z�7P�_f�aZ"bd � �e�'f`g M _·Y\`�U�oO_�y�r�pq]5`q[\b/]�[\`5mHx�digA5\[^b/]5dfUXg�U�oX_/`;��] k mL]QmOxixcg\U65\_epQUOu�m}p�[\yc]5`�_/_·UOu k _edf� k ]��yM_exfUXg\��]5U�] k _¦p5mHW _¦`�dfg\�A;«�_/]·] k _¦u�mOb2]�] k mH]·]43«U�g\U65\_ep�óºmOgA5d�wy�_/xiUXg\��]�UZ] k _»p�mOWZ_`�dfg\��y�_�5^_eg\UO]�_�5�y£r,ó�á�½�4;@ItUO]�_¦] k mH]Já�Â�dip·mOgº_�ah[^dfoHmOxi_/g\be_¦`q_ex¹mL]5diUOgO;x+mOpq_�T+mOpq_,b«�váã�ôcs= j�k _zpq[\y^]5`q_e_�b/UXg\p�dfpq]�p¾UOuDm�pqdig\�Oxi_&g\U:5^_O{ k _eg\b/_z] k _ k rcYMUO] k _epqdip"dfp]5`qdfohd¹mHxixfrZp�mH]5dfpFV�_�5O;vsgA5\[^b/]5dfUXg�ah]5_/Yjb��°4 �kc�=@?Ï`qUXW ] k _}digW5\[\b/]�diUXg k rhYMUO] k _/p�dfpe{Ïdfu�g\U65\_epJóBmOgA5>��y�_/xiUXg\�z]�U] k _Zpq[\y^]�`�_e_ `�UhUO]5_�5 mH]»mºb k dix95 ù UOugåc{] k _egzó�á�¤�4; acdfg\be_ mOb/]�diUXgÍ��UOuVg\U:5^_�Ð dip}g\UH]_eg\mOy\xi_�5){ ¬k¿�åsá¢� ù ¿�åc{cmOgA5 k _eg\b/_håsá�Â;� ù ¿�å6;Qacdig^be_*�¯4I�^{hdfu)] k _¾ximOpq]«b k dix85�UOu] k _¾`qUcUH]Vdfp�w] k _egv�Lãá å6;Dacdig^be_&mOb/]�diUXg���UOu��:dip�g^UO]·_eg�mHy\xi_�5){'¬k¿ b�� ù ¿���c@á´åh{�dU;Õ_K;*åsá�½�4;½?wdig�mOxfxfrO{cdªu ù

���

Page 19: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

dip$g^UO]$] k _·ximOpq]Qb k dfx95�UOuwåc{ôú­¬k¿ ù ãá ù ;$ahdig\b/_tmHb/]5dfUXg�~¦UOu ù dfp$g\UO]Q_/g�mOy\xf_�5){³¬k¿ b�� ù ¿ ù c*á ú�¬k¿ ù {3 k dfb k dfW Y\xfdi_/p ù á�Â@ú�¬k¿ ù ;

x«r�]�`5mOg^p�df]�dfohdf]sr�UOuOá�Âe{ô3V_ k m¨oX_·] k mH]�å¤á�Â�� ù ¿�å�á�Â�ú­¬ô¿9b«� ù ¿�åkc*á�Â0¿�¿�¿6á�Â�� 3 k _e`�_J��dfp] k _¾x¹mHpq]«b k dix85 UOuOå:; j�k [\p/{\mOxfxMg^U:5\_/pVUOu�] k _�]5`�_/_¾`qUcUO]�_�5�mH]gå¦yM_exfUXg\�»]�U»] k _¾p�mOW _�`�dfg\�A;Ãh

l"y\pq_e`qoO_�] k mH]"_¨mOb k mOb2]5diUOg9UOuz±­ mOpqp�di�Og\p}m�pq[\beb/_ep�pqUX`¦] k mH]"dip"mL]¦m_5\dfpq]�mHg\be_�UOuDmL]WZUXpq]t�W;g?Ï[^`q] k _e`e{Ïpqdig\b/_&] k _»�O`5mOY k UOu:] k _&p�[\b/be_epqp�UX`t`�_/x¹mH]�diUXgºdip�mZ`�dig^��] k mH]·]5`�m¨oX_e`qp�_/p}m`�UhUO]�_�5 p�Y�mHg\g\dig^�º]�`�_/_�W�mOdfg�]�mOdfg\_�5�y�r9] k _�mOb/]�diUXg^p}UOu� ����6{�] k _�xi_/g\�O] k UHuD] k mH]¦`qdig\�BdfpmH]·WZUXpq]t�Wb~}�� ��c�;�M _¦beUXg\b/xi[A5^_¦] k _¦Y\`�UhUOu3·df] k

@BA �C� � � � DCÄÅuIw �q� �\GQP�ZaG�� �IGJy\ÆÇ�¦�Ò�\P���_f�aZºK�PH�U� �K� ��m�op]��U_f���l���Ò�K�JGz�LKQ�&H GBm/PH���}T^�\�CGQPRXGQ�\GQP��,���U��]'x6�U�K��_U�q�`�LK¯±­ ÈPRG!�6�IH G��l�2���Ò�K�JG[NOH GQPRGJÍ?H��UTWVq�ÉN�_f�YHa_f�¥Ê�PH�Ux:�'V"b h

Ë Ì�)2$./�«�-.+.1�$dê ëìª�¬ ­Z(/Í'®

vsg�] k dip�Y�mOYM_e`/{�3V_l5\_eWZUXg\pR]5`5mL]5_�5�]43VU�_�XZbedf_eg�]¨{Mg\UXg\W mOpFEhdfg\��u�mO[\xf]R�±]�UXxi_/`5mOg�]�mOxf�XUX`�dª] k WZpuÄUX`$`q_eUX`q��mOg\d87edig^�"pqrhpq]�_eW g\U65\_/pDdfg�]5U"]5`q_e_/p«mHgA5�`�dig^�Xp$`�_/p�YM_eb/]�dfoO_exfrK; j�k _�mOxf�XUX`�dª] k WZpÌ3«_e`q_5\_/p�di�Og\_�5Z_�Y�_eb2]5dfoO_exªrz[\pqdig\�}]43«U&uÄUX`qW�mHx^WZ_/] k U:5\pQmHgA5p3V_/`�_·g\UO]�_�5�]5U¦Y�UOp�p�_/p�pDp�_2oX_e`�mOx�uÄ_¨mL�]5[^`�_ep�] k mL]¸mO`q_VximOb�E£dig\��dig&_�Ph]�mHg£]�5\dipR]5`�dfy\[^]�_�5»mOxi�XUO`�df] k WZp)uÄUX`wpqY�mOg\g^dig\��]5`�_/_Vb/UXg\pq]�`�[\b2]5dfUXgmOgA5�`�dfg\��_eW�y�_�5A5\dig^�A;

j�k _@V�`qpq]6uÄUX`�W mOxXWZ_/] k U65s3VmOp�y�mOpq_�5�UOg»b/UXW Y^[^]5dfg\��] k _QpqrhpR]5_eW pR]5`�[^b/]5[^`�_epw`�_/p�[\xª]5dig^�uÄ`�UOW mOg�r g£[\W�y�_/`»UOu+p�diW�[\xf]5mOg\_eUO[\p}u�mO[\xf]&Uhbeb/[\`�`q_eg\b/_ep�i$] k dip&W _2] k U65`3VmOp�mOY\Y\`qUXY\`�dimH]5_3 k _/g p�[\b k b/UXWZY\[^]�mL]5diUOgS3VmOp�_emOpqrO{$mOp¤3+mOp&] k _ b¨mOpq_�dfg�W mOdig�]�mHdig\dfg\�0]5`q_e_ep¤3 k _e`q_�] k _YM_e`q]�[\`�yM_�5 pqrhpR]5_eW4pR]5`q[\b/]�[\`�_�3+mHp&`q_¨mK5^dixfr�p k U�3·g ]5UºyM_ZmBuÄUO`�_epR]¦UOuD]5`�_/_ep�; j�k _ pq_eb/UXgA5uÄUX`qW�mOx�WZ_/] k U65�W mK5\_Dg\U"mOpqp�[\WZY^]�diUXg\p:mOyMUX[^]�] k _Dpqrhpq]�_eWæpq]5`q[\b/]�[\`�_V`�_epq[\xf]�dig\�·uÄ`�UOW(u�mO[\xf]Uhbebe[^`�`�_/g\be_/p�i�] k dip�W _2] k U65l3VmOp¸mHY\Y\`�UOY\`�dimH]5_*3 k _/gzbeUXWZY\[^]5mH]5dfUXg&UOu\] k _«pRrcpR]5_/W pq]�`�[\b2]5[\`q_dig ] k _ Y\`�_/p�_/g\be_0UHu+u�mO[\xª]5ps3+mOp»_edª] k _/` k mH`!5 UX`¦rhdi_/x95\_�5 m�b/UXWZY\xi_�P pq]5`q[\b/]�[\`�_ ] k mH]¤3VmOpdig\mOY\Y\`qUXY\`�dimH]5_tuÄUX`u5\_epqdi�Xg�Y\[\`qY�UOp�_ep/{MmOpL3+mHp�] k _¦b¨mOpq_&dfgºW�mOdfg�]�mOdfg\dig\�»`�dfg\�Xp�;

M _�`q_eb¨mHxix$] k mL]zm!pR]�mOgW5�mO`!5 mOY\Y\`qU�mOb k ]�U9`�_/beUXg:V��X[\`�mH]5dfUXg�dfg`5\dfpq]�`�diy^[^]5_�5�pqrhpR]5_eWZpdip�]�U _/xi_/b/] UXg\_ºg\U65\_�mOpZ] k _ºxi_emK5\_e`/{«] k mH]�3·dixfx+beUXg�]�`�UXx+] k _�Y^`�Uhbe_epqp UHu"beUOgWV��X[\`�mH]5dfUXgO;�_¨mK5^_e`�_exi_/b/]�diUXg�dip�`�_emK5\dixªrºmOb k df_/oO_�59y�r�_exf_eb/]�dig\��] k _»`qUcUO]�UOu:] k _&`�UhUO]5_�5!pqY�mOg\g\dfg\��]5`�_/_mOp¾] k _�xi_emK5\_/`�;»l"[\`}mOxf�XUX`�dª] k W· ���� b¨mHg){�] k _e`�_2uÄUX`�_H{y�_zmOxipqU�ohdi_�3«_�5 mOp}m0g^UXg\W mOp!E£dig^�

���

Page 20: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

u�mO[\xª]q�ô]5UXxf_e`5mHg£]Vp�UXxf[^]5dfUXg0]5U�] k _¦xi_¨m<5\_e`·_exf_eb2]5diUOgBY\`�UXy^xi_eW>;M _�mHxip�U�g\UH]5_}] k mL]tUO[\`·Y\`�UhUOuÄp·UOu¸b/UXg�oX_/`��X_/g\be_l5\U�g\UH]J5^_eYM_egA5�UXg�] k _»mOp�pq[\W Yc]5diUOg

UOu&u�mOdi`qg\_epqpBuÄUX`B_�Pc_eb/[^]5dfUXg UHu�b/UXg�]5dig£[\UO[\p�xªrI_eg�mHy\xi_�5 mOb2]5dfUXg\p�;�M _ k m¨oX_ ] k [\pºu�mO`ºmOpF�p�[^W _�50u�mOdi`qg\_epqpVUXg\xªr�]5UzpqdiWZY\xidªu rz] k _¾_�PcY�UOp�df]�diUXg ;@t�UX`q_eU�oX_/`e{\] k _e`�_¾_�PcdipR]+`�_�V�g\_/W _/g£]�p�UOuÐsÍ�Î mHgA5���Ð ] k mH]¸rhdi_/x95z`q_¨mK5�Î�3·`�df]�_�mH]�UXW dfbedª]sr�mHxi�XUX`qdf] k W p] k mH]DmO`q_+g\UXg\W mOpFEhdfg\�"u�mO[\xª]q�]5UOxi_e`�mOg�]zmHpl3«_exix~;>M _0b/UXgqÀq_eb2]5[\`q_�] k mH]�] k _�`q_ep�[^xf]5dfg\�!`q_¨mK5 Îq3·`�dª]5_0mL]5UXWZdib/df]sr�Y\`qUX�X`�mOW pb¨mHg�yM_¦g\dib/_exfr ]5`�mOg\p�ximH]5_�5ºdig�]5U�g\UXg^W�mOpFE£dig\��u�mO[\xª]q�ô]5UXxf_e`5mHg£]VW _/p�p�mO�X_¦Y�mOpqp�dig^�ZY^`�UX�X`�mOWZp�;

M k dfxi_g3«_ k m¨oX_·uÄUcb/[\p�_�5 UO[\`QmH]�]�_eg�]5dfUXg�UXg�] k _�5^_ep�df�Xg�UOu�g\UXg\W mOp!E£dfg\�"u�mO[\xª]q�±]�UXxi_/`5mOg�]`�_/beUXg:V��X[\`�mH]5dfUXg�mHxi�XUX`qdf] k W ptdig�] k dip¦Y�mOYM_e`/{wdª]�3·dixix:y�_p3«UX`q] k 3 k dixi_�]�U�_�Pc]�_egA5 UX[\`¦g\UXgh�W mOp!E£dig^��u�mO[\xª]q�±]�UXxi_/`5mOg�]VmOxi�OUX`�dª] k WZp$]5U�UXy^]5mOdig�W�mOpFE£dig\��u�mH[\xf]R�±]5UOxi_e`�mOg�]«mOxi�XUO`�df] k WZp�i�] k mL]dip/{�mOxf�XUX`�dª] k WZp«] k mH]�W mOp!EZ] k _¦YM_e`q]�[\`�yM_�5�pq]�`�[\b2]5[\`q_¦uÄ`qUXW ] k _¦beUhUXY�_/`5mH]�dfoO_}W _/b k mOg\dfp�WZp] k mH]·`�_/xfrBUXgB] k _¦pq]5`q[\b/]�[\`�_<;

vsgZp�UXWZ_�b¨mHp�_ep/{63«_�mOg�]5dfbediY\mH]5_+] k _·`�_epq[\xf]QUHu�_�Pc]�_egA5^dig\�&g\UXg\W mOpFEhdfg\�&mOxi�OUX`�dª] k WZp3·dfxixyM_ºmOxi�XUO`�df] k WZp&] k mH]�mO`q_0yMUO] k W mOp!E£dig^��mOgA5Íg\UXg^W�mOpFE£dig\�9u�mO[^xf]q�ô]5UXxf_e`�mOg�]�; j�k _,5\_/p�df�XgUOuDp�[^b k mOxf�XUX`qdf] k W p�dip"WZUO]�dfoHmH]5_�59y�r9] k _�dig\pqdi� k ]¾] k mH]}] k _zu�mO[\xª]q�spqY�mOg9UHu+mOg mHxi�XUX`qdf] k Wb�g\mOW _/xfr>Î�ctg\_e_�5 g^UO]}yM_�[\g\d9a£[\_>R��/�F�qTU;&v±]"uÄUXxfxiU�3·p"Wz[^xf]5dfY\xi_¦u�mO[\xª]q�±p�Y�mOg^p"W�m¨r�y�_�mHp�p�UL�bedimH]5_�5ò3·df] k mOg mOxf�XUX`qdf] k Wv; |t_/g\be_H{Vdª]�dip�YMUXp�pqdiy\xf_�] k mH]ZmOg mOxi�OUX`�dª] k W dip�g^UXg\W mOp!E£dig^�]5UOxi_e`�mOg�]J3·dª] k `q_epqY�_/b/]}]5U UXg\_zUHu¸] k _/p�_zu�mO[^xf]q�±p�Y�mHg\p¾mHgA5�g\UXg\W mOpFEhdfg\� ]�UXxi_/`5mOg�]�3·df] k `�_8�p�YM_eb2]t]�UZmOg\UO] k _e`�;

l¾] k _e`º_�Ph]5_/g\p�dfUXg\p,3·dixfx"dig\b/xi[A5^_�_�Ph]5_/gA5\dig^� ] k _ g^UXg\W mOp!E£dig^�Íu�mH[\xf]R�±]5UOxi_e`�mOg�]BmOxf�XUH�`�dª] k WZp�p�U ] k mL]Z] k _/r mO`q_ºp�_eb/[\`�_v5\[\`qdig\� ] k _�YM_e`�dfU:5ÍUOu¾beUXg�oO_e`��O_eg\b/_K;�ac_eb/[\`�dª]sr dip�_epF�YM_ebedimOxixªrBdiWZYMUX`q]5mOg�]·dig!WZU65\_e`qg!pqrhpR]5_eWZp�3 k _/`�_z`q_eb/UXgWV��X[^`5mH]�diUXg�Ucb/be[\`qptuÄ`�_�a£[\_eg�]5xªr9mHgA5] k [\p·] k _&pRrhpq]5_/W.dip�UOu ]�_eg�digBoh[\xig^_e`5mHy\xi_}pR]�mH]�_ep�;

Ï $ �����³²7Ð��a��Ñ�� � �³�'!�(\Ò M�_$] k mOgAE¾] k _DmOg\UXg�rhWZUX[\p�`�_/uÄ_/`�_/_ep6uÄUX`)] k _/di`6beUOg\pq]�`�[\b2]5dfoO_p�[^�X�X_epR]5dfUXg\p�;

ëìª�Ókªh(@ªh$./�ª�®

ØÂÝ�Ú&ìt¼�ìD¢F �¢q¤V¤��h�}ç�¼ ë ¼ ë  �¯h�£¤X´'Ô Ó ³� ��R¯�¢F�¸¤��£�}²5 ��Lµ���¢R���8�£²5�#Õ6ì ¬i �¯£�£�£¤¨�F�© ��t �¬c¬i¤�¯h³��±°Ä�s �³���¢R¤��H�²5 �¥}¡h¯£�F�©����ÖX´�×JØ�Ø�ØÚÙCÛJÜ¡Ý"ÞRÜUß�à-áYâ¡Ý"Þ¼â¡Ý9ã�âåäRà-æ�Ü¡ÛLçMØ�Ýéè#á>Ý�ç¤çIÛ§á>Ýéè Ý�ê"ë±Ý�ÝQì1ë±Ý�ê#ê�Þ�ìq´6¡£¡Ï¼wÝ�å�Ý8èQí

���

Page 21: 0& 1 )2$web.cse.ohio-state.edu/siefast/group/publications/trees... · 2001. 4. 28. · #%$'& (*),+.-./0& 1 )2$ TVUhUXY _/`5mH]diUXgºyM_/] 43 «_e_/g9] k _&g\U 65 \_ep UOu 5 ^dipq]`dfy\[^]5_

Ý�å�Ô�îH¼Ø×Ô/Ú&ìt¼£ìD¢F �¢q¤X´�Ôsì ¬i �¯£�£�h¤¨�F�� ��z �¬�¬¹¤�¯£³��±°Ä�s �³©��¢R¤��L�Q²5 �¥¦¡h¯��F�©����ÖX´³ï�ð\ñóò2ñ ò�áÃÞ¤ÞIçIÛ`à&Ü�à-á-â¡Ýh´hàQ§��nôV�£�°µ���¢R�F�©��­z �¬�à��5¿�¤��D¤¨�«ìV¯£�s�F�ª�ºë±Ý�ê#ê�Ô�ìq¼

Ø×Þ/Ú&ìt¼wì«¢F �¢R¤X´$ç�¼ ë ¼ ë  �¯h�£¤X´$¤��£� ë ¼wâ6¤¨¢F��§��8�s��´ÉÔ Ó  ��h�s�s¢R¤��©�H�&�F¤¨�F�©�F¬i¤�²5�F�� �� ¤��&¤B®c¤��F�©�}¬i �¢���8�F�©���£�©���!�� ��£¥¦¤��sÃX�©����¬i¤�¯h³��±°Ä�s �³���¢R¤��£²5��ÖX´�õ"â¡ö¿Û§Ý³Ü#÷^âJä}ønáóè#ð:ã#ù"ç§çLú9û2ç�à-æ�â¡Û¤üpÞq´*ë±Ý�ê#êeÖ��s ¤¨¡£¡\�8¤¨¢`ì§ýeï�ÛåâQߧç¤ç¤ú¡á>Ýéè¡ÞMâåä*à>ð¿çMþIÿCà>ð7קÝaà�çIÛ§Ý�Ü#à-á-â#ݳܡ÷���â¡ÝQäIçIÛJçIݳߧçBâ¡Ý�ònáÃÞ`à-Û`á��Rö"à�çLú���â���ù³ö"à�çRÛã��cÞ`à�ç��Þ^ë±Ý�ê#êeÖéìq´\¡£¡Ï¼XÖLÔeÖcíLÖLÞXݨ¼

Ø Ö¨Ú�Q¼^� ¼^Û+� �sÃO�F�s¢R¤X´OÔRÙX�8³�¬ª°��F�F¤¨®h�©³©�� 8�ª���¦�s­X�s�s�8¥¦�+�©�Z�F¡h���s�� �¬w�£�©�s�s¢R�©®h¯��s�8��²5 ��H�s¢F �³ªÖX´���â�����ö\Ýaá��ߤÜ�à-á-â¡ÝCÞ�âåä�à>ð¿ç������.´£â �³Ä¼MÝQîH´��« �¼MÝ�ݨ´h¡£¡M¼��eÖLÞ/°��eÖ�Ö�ë±Ý�ê�î/Öéìq¼

Ø×è/Ú&ê:¼��«¼��¸¤��s�F¤��£�Ä´��q¼ ° ��¼"!6�8��´�¤��£����¼ °�ä·¼ Ó §��8��´nÔsìæ²�³©¤��F�¾ �¬«�ª�£§���¢F�8�H�F³�­0¬i¤�¯h³��±°Ä�s �³���¢R¤��H�}�£�©�±°�s¢R��®c¯��s�8�z¡£¢F ���¢R¤�¥&�LÖX´�×JØ�Ø)Ø¢Ù"ÛJÜ¡Ý"ÞIÜ�ß�à-áYâ¡Ý"Þ*â¡Ý�ã�âåäRà-æ�Ü¡ÛLç�Ø�Ý\èQèUñMÝ5Öaë±Ý�åUì�ë±Ý�ê$#$#�ìq´c¡£¡M¼ÏÝ5ÖLÞXݧíÝ5Ö�ÖLÔO¼

Ø%�/Ú&ä·¼ ë ¼ ë ¤�³©³ª¤¨��§���¢8´�ß�¼Dì�¼�&V¯£¥t®h³�����´�¤��£�Íß�¼Dç�¼VÙO¡c��¢R¤X´MÔsì��£�ª�s�s¢R��®h¯£�s�8��¤�³©�� �¢R���F§£¥ ¬i �¢¥¦�©�h�©¥t¯h¥"°Ä�w�8�©��§L�z�s¡h¤��£�h�©�����s¢R���8�LÖX´'�(��� ÙCÛåÜ#Ý"ÞRÜ�ßQà-á-â#Ý"Þ°â¡Ý¹ï�Ûåâ¤è#ÛJÜ�����á>Ýéè*)'Ü¡ÝéèUñ�Ü¡Ý�úã��cÞRñ\è"ë±ÝQì�ë±Ý�ê$#�Þ�ìq´c¡£¡M¼+�$�Qí¿î#îH¼

Ø î2Ú&ìt¼\ì«¢F �¢R¤z¤��£��ç�¼ ë ¼ ë  �¯£�£¤X´/ÔsÛ+�©�s�s¢R�©®h¯��s�8� ¢F�8�s���LÖX´�×JØ�Ø)ØSÙCÛåÜ#Ý"ÞRÜ�ßQà-á-â#Ý"Þ[â¡Ý,��â���ù³ö"à�çIÛ¤ÞÖLÞ"ëYê�ì2ë±Ý�ê#êeÖéìq¼

Ø%#/Ú ë ¼/â6¤¨¢F��§��8�s��´�ÔRÙO�8³©¬ª°��s�F¤¨®c�©³©�� 8¤¨�F�� ��·®H­�³� X²�¤�³L²q§��8²FÃX�©���V¤��£��²5 �¢F¢R�8²5�F�� ��CÖX´UïOð\ñóò�ñéò�áÃÞ¤ÞIçIÛ`à&Ü�à-á-â¡Ýh´ç�¤��F�F¤�²R§O¯£�s���s�F�-�±�£�s�F���F¯£�s�V �¬à��8²R§£�£ �³� ���­ºë±Ý�ê#ê�Ô�ìq¼

Ø ê/Ú&ä·¼cß���¢q³©¥¦¤���´�ÔsìV�Z¤�³��� �¢R�©�F§£¥(¬f �¢«�£�©�s�s¢R�©®h¯��s�8��²5 �¥}¡h¯��F¤¨�F�� ��Z �¬�¤&�s¡h¤��£�£�ª���t�s¢R�����©��¤����5¿O°�s�8�£���8�.�Mì-�;ÖX´Cûná>Ýaà>ð��(��� ò�Ü#à&Ü/��â�����ö\Ýaá-ߧÜ#à-á-â#Ý"Þã����5ù"âcÞ§á>ö0��´£â �³ ¼�Ô¨åX´+�D �¼Cî[ë±Ý�ê$#�è�ìq´¡£¡Ï¼�Ö�ÖcíOè�ÔO¼

ØÂÝ�åeÚ21�¼ °�ç�¼3&54�8³©¤¨¢F­B¤��£�Bç�¼ÏäD¤8­X�£¤�³ ´;Ô±âV�©¢F�F¯£¤�³�¢R�©����²5 ��£�F�s¢R¯£²5�F�� ��B�©�0¡c¤¨¢R¤�³©³��8³)�£�©�F�s¢R��®h¯��s�8���s­X�±°�s�8¥¦�LÖX´^ç�¼ Ó  ��F�£¤¨¢R�¯ëi�8�ϼ�ìq´�ï/Ü¡ÛJÜ¡÷>÷|çI÷�ï�Ûåâ�ß`ç`Þ§Þ§á>Ýéè�´6�³©�s��µX����¢«ÙX²��©�8�£²5��´ÏÝ�ê$#$#O´c¡h¡Ï¼£Þ�Þ�ÞQíOÞeÖLèO¼

ØÂÝ�Ý�Ú&ß�¼ÏäQ ��s�8�h�s�F���8§£³ ´31£¼�ä·¼Ïê)��ÃX�s�8³ ´Ï¤��£�Bìt¼�&D �³ª³©������¢8´�Ô7�±�L�s�8³©³ª�����8�L����¢q¤¨¡h§£�IÕ+�������: �¢FÃX�� �¬w¶c�£���s�¤�¯��s �¥¦¤¨�F¤�²�¤¨¡c¤¨®h³��¾ �¬w�s �³�µX�©���&��¢R¤¨¡h§�¡£¢F �®h³©�8¥¦�LÖX´\ä·¼ Ó ¼^äD�8¤��¥ëi�8��¼�ìq´�8�ÛJܧùað�Ù'ð¿çLâ¡Û9�7Ü¡Ý�ú��â���ù³ö"à-á>Ýéè�´^쫲�¤����8¥&�©²·ß6¢R�8�F��´ÏÝ�ê�î¨ÔO´h¡h¡Ï¼hÔXÝ�êQíOÔ$��èO¼

ØÂÝ8Ô/Ú&ìt¼/ì«¢F �¢R¤Q¤��£��ì�¼�ÙX�©����§£¤��Ä´aÔR½V¡£�F�©¥&¤�³ ´/�� ��h¥¦¤��sÃX�©���¸¬i¤�¯h³��±°Ä�s �³���¢R¤��H�M¢F�8²5 ���¶h��¯�¢R¤¨�F�� ��· �¬O�s¢R���8�¤��£�»¢R�©�����¤ÖX´;:Oã=<�Ù³ç¤ßRðUÝCáYߤÜ#÷?>5ç�ù¿â¡ÛRà���פã+>@�"��ÙA>CB$D$�åþEDFDIÿ"ýh¤�¡£¢F�8³©�©¥&�©�£¤¨¢F­tµ���¢R�F�� ���¤¨¡£¡\�8¤¨¢R��©�zï�Ûåâ�ß`ç¤ç¤ú¡áÃÝ\è¡Þ�âJä;קÝaà�çRÛ`ݳÜ#à-áYâ¡Ý³Ü#÷G��â¡ÝQäIçIÛJçIݳߧç�â¡Ýzû�çIà-æ�â¡Û§ü�ï�ÛJâ#à&â�ߧâ¡÷�Þq´\¡£¡Ï¼£Ô�ÔXÝ�°ÀÔ�Ô$#O´Ý�ê#êeÖ�¼

�O�