<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\def\FAPESP{\textsc{fapesp}}
\def\CNPq{\textsc{cnp}q}
\def\CAPES{\textsc{capes}}
\def\CAPESDAAD{\textsc{capes-daad}}
\def\CAPESCOFECUB{\textsc{capes-cofecub}}
\def\DAAD{\textsc{daad}}
\def\GMD{\textsc{gmd}}
\def\FINEP{\textsc{finep}}
\def\MCT{\textsc{mct}}


% 
% \setlength{\parindent}{0ex}
% \setlength{\parskip}{0.7pc}
% \setlength{\textwidth}{15cm}
% \setlength{\textheight}{20.5cm}
% \setlength{\topmargin}{0.3cm}
% \setlength{\headheight}{0cm}
% \setlength{\headsep}{0cm}
% \setlength{\oddsidemargin}{0.7cm}
% \setlength{\evensidemargin}{0.7cm}

                %%%%%%%%%%%%%%%%%% para Bolsa Pesquisa CNPq %%%%%%%%%%%%%%%%%%%%

\newcommand{\dmoldura}[1]{{\noindent\fbox{\fbox{\parbox[t]{14.0cm}{ #1 }}}\vspace*{.5cm}}}

% 
\setlength{\parindent}{0ex}
\setlength{\parskip}{0.5pc}
\setlength{\textwidth}{14.4cm}
\setlength{\textheight}{19 cm}
% \setlength{\topmargin}{0.3cm}
% \setlength{\headheight}{0cm}
% \setlength{\headsep}{0cm}
 \setlength{\oddsidemargin}{0.8cm}
 \setlength{\evensidemargin}{0.8cm}

                %%%%%%%%%%%%%%%%%% para Bolsa Pesquisa CNPq %%%%%%%%%%%%%%%%%%%%
\begin{document}
\centerline { \bf {\sc Documento 3}} 
\begin{center}
\dmoldura{
\centerline {\phantom{a} }
\centerline {\Large \bf {\sc Workshop on Combinatorics, Algorithms, and
    Applications }} 

\centerline { {1 a 5 de setembro de 2003}}
\centerline {{Ubatuba, SP}}
\centerline{\phantom{a}}
}
\end{center}

%\vspace{0.3cm}

\section{Introdução}

O {\it Workshop on Combinatorics, Algorithms, and Applications} é um evento
organizado no âmbito do projeto ProNEx (Programa de Apoio a Núcleos de
Excelência) "Complexidade de Estruturas Discretas," financiado pelo MCT/CNPq
(Proc. CNPq 664107/1997-4), e sob a coordenação de Y. Kohayakawa.  Informações
sobre este projeto (membros, relatórios, publicações) e este evento podem
ser encontradas em
\begin{verbatim}
           http://www.ime.usp.br/~yoshi/pronex/
           http://www.ime.usp.br/~yoshi/pronex/Workshop/
\end{verbatim}
O evento será realizado no período de 1 a 5 de setembro de 2003, em Ubatuba, e
contará com a participação de grande parte da comunidade brasileira da área de
Combinatória e Teoria da Computação.

Foram convidados cerca de 15 pesquisadores internacionais, a maioria
deles grandes expoentes da área de Combinatória e Teoria da
Computação. Estes irão contribuir cada um com uma ou duas palestras em
quatro grandes áreas:

\begin{itemize}
\item [--] {\bf Biologia Computacional} {\small (M-F. Sagot, E. Ukkonen)}
  
\item [--] {\bf Combinatória Probabilística} {\small (D. Duffus, A. Frieze, P. Raghavan, B. Reed)}
  
\item [--] {\bf Enumeração/Análise de Algoritmos} {\small (M. Kiwi, B. Richmond, A. Viola)}
  
\item [--] {\bf Otimização Combinatória} {\small (G. Cornuéjols, A. Frieze, P. Raghavan, B. Reed)}
  
\item [--] {\bf Teoria dos Grafos} {\small (G. Cornuéjols, L.H. Kauffman, B. Reed, J.
  Spinrad, C. Thomassen)}

\end{itemize}



\section{Comissão Organizadora e Comissão de Programa}

A comissão organizadora, responsável por todos os arranjos locais e
pela implementação do evento, é composta dos seguintes professores: 

\begin{itemize}

\item[]  Carlos Eduardo Ferreira {\sc (dcc-ime-usp)}
\item[]  Cristina Gomes Fernandes {\sc (dcc-ime-usp)}
\item[]  Flávio Keidi Miyazawa {\sc (ic-unicamp)}
\item[]  José Coelho de Pina Jr {\sc (dcc-ime-usp)}
\item[]  Yoshiharu Kohayakawa{\sc (dcc-ime-usp)}
\item[]  Yoshiko Wakabayashi {\sc (dcc-ime-usp)}


\end{itemize}

A comissão de programa, responsável pelo formato do evento, pela escolha e
vinda dos palestrantes convidados, é composta dos seguintes professores: 

\begin{itemize}

\item[]  Carlos Eduardo Ferreira {\sc (dcc-ime-usp)}
\item[]  Celina M. H. Figueiredo {\sc (dcc-im.ufjr)}
\item[]  Cláudio Leonardo Lucchesi {\sc (ic-unicamp)}
\item[]  Marcelo Henriques de Carvalho {\sc (dcc-ufms)}
\item[]  Sóstenes Luiz Soares Lins {\sc (dmat-ufpe)}
\item[]  Yoshiharu Kohayakawa   {\sc (dcc-ime-usp)}
\item[]  Yoshiko Wakabayashi  {\sc (dcc-ime-usp)}

\end{itemize}

\section {Programa}

O evento segue os moldes de uma escola em Teoria da Computação, contando com a
presença de vários pesquisadores de altíssimo nível, que contribuirão cada um
com uma palestra plenária, para uma audiência geral de Teoria da Computação, e
uma palestra específica, mais voltada às pessoas que trabalham na área em
questão. Outros pesquisadores colaborarão apenas com uma plenária ou palestra.

A programação diária do evento consistirá basicamente de 3 palestras
plenárias, cada uma com duração de uma hora, e sessões paralelas contemplando 
tópicos mais específicos.

A diversidade das áreas contempladas pelo evento reflete a diversidade das
áreas em que trabalham os membros do projeto. Essa diversidade, aliada ao alto
nível dos palestrantes convidados, torna o evento de interesse para toda a
comunidade brasileira de Teoria da Computação. Trata-se também de uma ocasião
rara em que contaremos com a presença de tantos pesquisadores desse calibre
num mesmo evento. Será uma excelente oportunidade para que os alunos de
pós-graduação da área possam conhecer e contatar esses pesquisadores.

Vários desses palestrantes estrangeiros convidados colaboram ou colaboraram
com membros da comunidade brasileira em Combinatória e Teoria da Computação. A
presença desses convidados no evento criará condições e oportunidade para que
tais colaborações se intensifiquem e que novas colaborações sejam iniciadas
com outros membros da comunidade brasileira.

A lista de palestrantes convidados é a seguinte:


\begin{itemize}

\item {\it Gérard P. Cornuéjols},  Carnegie Mellon University.
\item {\it Dwight Duffus},  Emory University.

\item {\it Alan Frieze},  Carnegie Mellon University

\item {\it Louis H. Kauffman}, University of Illinois at Chicago.

\item {\it Marcos Kiwi},  Universidad de Chile.

\item {\it Prabhakar Raghavan},     
   Department of Computer Science, Stanford University e Verity.

\item {\it Bruce Reed}, School of Computer Science, McGill 
  University
  
\item {\it Bruce Richmond}, Dept. of Combinatorics \&amp; Optimization,
  Faculty of Mathematics, University of Waterloo.


\item {\it Marie-France Sagot},  INRIA, Rhône-Alpes.

\item {\it Jeremy Spinrad}, Vanderbilt University.

\item{\it Jayme Szwarcfiter}, NCE-RJ.

\item {\it Carsten Thomassen} (a confirmar), Technical University of
  Denmark.

\item{\it Esko Ukkonen},      
     Department of Computer Science, University of Helsinki.

\item {\it Alfredo Viola}, Universidad de la República.
  
\end{itemize}


Outros pesquisadores do exterior demonstraram interesse em participar, sendo
muito provável que outros nomes se juntarão a esses. Entre eles destacamos:
U.S.R. Murty e Martin Loebl. Apresentamos a seguir um breve resumo do perfil
de alguns desses  pesquisadores.


\section{Justificativa sobre o pedido}

Embora o evento esteja sendo organizado no âmbito do projeto ProNEx (Programa
de Apoio a Núcleos de Excelência), financiado pelo MCT/CNPq, os participantes
deste projeto estão fazendo um esforço para reunir outros membros da
comunidade brasileira que atuam em Teoria da Computação. A vinda dos
pesquisadores estrangeiros que mencionamos certamente irá trazer muitos
benefícios para toda a comunidade brasileira da área.


O projeto ProNEx irá custear as despesas de seus membros (incluindo
alunos de pós-graduação), e as passagens dos convidados estrangeiros.
Essas despesas serão da ordem de R\$ 60 mil. Estamos solicitando à
FAPESP 75 diárias (5 pernoites para 15 pesquisadores) para financiar a
estada desses convidados.




\section{Breve resumo sobre os convidados estrangeiros}

\begin{itemize}

\item  Alan Frieze

\begin{itemize}

\item Carnegie Mellon University.\\
 \texttt{http://www.math.cmu.edu/\textasciitilde af1p/} \\ 
 Em 1991 recebeu o {\it Fulkerson Prize} em Matemática Discreta - prêmio
 concedido pela {\it American Mathematical Society} e o {\it Mathematical
   Programming Society}.  Prêmio recebido juntamente com Martin Dyer e Ravi
 Kannan pelo artigo {\it ``A random polynomial time algorithm for approximating
   the volume of convex bodies''}, {\it Journal of the Association for Computing
   Machinery} 38 (1991) 1-17.  Em 1997 foi eleito {\it Guggenheim Fellow}.

  Áreas de interesse: combinatória, otimização discreta e teoria da
  computação. Presentemente, tem focado a sua pesquisa nos aspectos
  probabilísticos dessas áreas. Em particular, no estudo das propriedades
  assintóticas de grafos aleatórios, análise de caso médio de algoritmos, e
  algoritmos aleatórios. Seus trabalhos recentes incluem conntagens
  aproximadas e cálculo de volume via passeios aleatórios; encontrar caminhos
  disjuntos em grafos expansores, e investigação da teoria de anti-Ramsey e
  estabilidade de algoritmos de roteamento.

  O {\it MathSciNet (Mathematical Reviews on the Web)} registra 201 publicações
  deste pesquisador.

\end{itemize}

%-----------------------------------------------------------

\smallskip

% \begin{itemize}

\item Louis H. Kauffman     
  
\begin{itemize}
   
\item  University of Illinois at Chicago. \\
   \texttt{ http://www2.math.uic.edu/\textasciitilde kauffman/} \\
  % Ph.D. Princeton University, 1972.
     Detentor de vários prêmios e honrarias. {\it Lester R. Ford Award of the
     Mathematical Association of America (1978) in expository writing} pelo
   artigo {\it ``Immersion and Mod-2 Quadrataic Forms''}, {\it American Mathematical
     Monthly} 84 (1977) 168-185; {\it NSF Fellow, Woodrow Wilson Honorary
     Fellow}, e outros.
   
   Editor do {\it Journal of Knot Theory and its Ramifications (World
     Scientific Publishers)}, desde 1991; editor da série de livros sobre {\it
     Knots and Everything} (desde 1991), editor associado do {\it Annals of
     Combinatorics}; membro do corpo editorial do {\it Cybernetics and Human
     Knowing} (desde 1995).
  
   Autor de 10 livros em teoria dos nós; e preparando 5 outros. 
   Tem cerca de 150 publicações listadas no {\it MathSciNet.} 

\end{itemize}


%----------------------------------------------------
\smallskip

\item  Bruce Reed

\begin{itemize}
  
\item
  School of Computer Science, McGill University. \\
  Até recentemente, Université Paris VI,  INRIA, França.\\
  \texttt{http://cgm.cs.mcgill.ca/\textasciitilde breed/} \\
  Áreas de interesse: combinatória, teoria dos grafos e otimização discreta,
  com ênfase nos aspectos algoritmicos e probabilísticos de problemas dessas
  áreas.  Tem cerca de 100 publicações listadas no {\it MathSciNet.}  Tem
  cerca de 8 artigos em co-autoria com pesquisadores brasileiros da área de
  combinatória. Trata-se de um pesquisador que tem colaborado intensamente com
  a comunidade brasileira na área (pesquisadores do Rio, de São Paulo, do
  Ceará), tendo inclusive organizado em 2001 o {\it CIMPA School on Algorithms
    and Combinatorics}, 12-16 e 21-24 de março/2001, Fortaleza, Ceará, com
  apoio do CIMPA (do governo francês).
 
 Tem cerca de 100 publicações listadas no {\it MathSciNet.}

\end{itemize}


%-------------------------------------------------------------
\smallskip
\item Bruce Richmond

\begin{itemize}   
\item   Dept. of Combinatorics \&amp; Optimization, Faculty of Mathematics,
  University of Waterloo.\\
  \texttt{http://www.math.uwaterloo.ca/CandO\_Dept/richmond.shtml}\\
  Áreas de interesse: enumeração assintótica e teoria dos números.

  Tem mais de 80 publicações listadas no {\it MathSciNet.}
\end{itemize}

%--------------------------------------------------------------
\smallskip


\item Prabhakar Raghavan 

\begin{itemize}      
\item  Dept. of Computer Science, Stanford University e Verity.\\
  %  Ph.D. UC Berkeley.
   \texttt{http://theory.stanford.edu/people/raghavan/}\\
   Membro do corpo editorial dos periódicos: {\it ACM Transactions on Internet
     Technology, Journal of the ACM, SIAM Journal on Computing, Web
     Intelligence and Agent Systems, Internet Mathematics.} Autor do livro
   {\it ``Randomized Algorithms''}, com R. Motwani,{\it Cambridge University
     Press}.

   Áreas de interesse: otimização combinatória e algoritmos aleatórios;
   recuperação de informação e mineracão de textos; análise de estrutura na
   Web. 
   
   Tem cerca de 70 publicações listadas no {\it MathSciNet.}

\end{itemize}


%----------------------------------------------------------------

\smallskip
\item Esko Ukkonen     
 
\begin{itemize}

\item   Dept. of Computer Science, University of Helsinki. \\
   Membro do Graduate School in Computational Biology, Bioinformatics, 
   and Biometry. \\
   \texttt{http://www.cs.helsinki.fi/u/ukkonen/}\\
   Áreas de interesse: Desenvolvimento e análise de algoritmos, 
   aprendizagem de máquina e biologia computacional.
   
   Tem cerca de 50 publicações listadas no {\it MathSciNet.}  A vinda deste
   pesquisador certamente atrairá o interesse dos pesquisadores da comunidade
   brasileira que atua na área de Bioinformática. Além desse pesquisador,
   convidamos a pesquisadora Marie-France Sagot (INRIA), que também atua na
   área de Bioinformática e está no momento em grande evidência, participando
   dos comitês de vários eventos na área e ministrando cursos em vários
   países. Pretendemos organizar no evento uma sessão especial na área de
   Bioinformática.

\end{itemize}

%---------------------------------------------------------------
\smallskip

\item Carsten Thomassen

\begin{itemize}
\item Professor of Mathematics, Technical University of Denmark.  \\
  \texttt{ http://www.mat.dtu.dk/people/C.Thomassen/} \\
  Membro do {\it Royal Danish Academy of Sciences and Letters}; Editor-chefe
  do {\it Journal of Graph Theory}; membro do corpo editorial dos periódicos:
  {\it Combinatorica, The Journal of Combinatorial Theory (Ser B), Discrete
    Mathematics,} e {\it European Journal of Combinatorics.} Recebeu em 1993 o
  {\it Lester R. Ford Award} (concedido pela {\it Mathematical Association of
  America}), além de várias outras honrarias.
   
   Áreas de interesse: Matemática discreta e Teoria dos Grafos.
   Tem mais de 160 publicações listadas no {\it MathSciNet.} 

\end{itemize}

\smallskip

%-------------------------------------------------------------------

\item Gérard P. Cornuéjols
\begin{itemize}
\item Dept. Mathematical Sciences, Carnegie Mellon.\\
% University Ph.D., Cornell University
\texttt{http://www.math.cmu.edu/people/fac/cornuejols.html}\\
 Áreas de interesse: otimização  combinatória  e teoria dos grafos, com ênfase
 nos aspectos algorítmicos. 
 
 A sua pesquisa corrente tem-se concentrado no estudo de grafos perfeitos,
 matrizes balanceadas, e na propriedade max-fluxo min-corte. Uma outra linha
 de pesquisa trata de problemas de otimização combinatória  NP-difíceis
 através do estudo de relaxações. Usando combinatoia poliédrica, tem feito
 contribuições significativas na teoria de cobertura de conjuntos, em problemas
 de roteamento de veículos e no problema do caixeiro viajante.

 Tem mais de 70 publicações listadas no {\it MathSciNet}.

\end{itemize}


\end{itemize}


\section{Publicações dos convidados em co-autoria com brasileiros}


Listamos a seguir algumas publicações dos convidados e participantes do
exterior em co-autoria com pesquisadores brasileiros da área de combinatória.

\begin{enumerate}

\item L. H. Kauffman, S. Lins. Temperley-Lieb recoupling theory and
   invariants of $3$-manifolds. {\it Annals of Mathematics Studies},
   134. Princeton University Press, Princeton, NJ, 1994. x+296 pp. 
 
\item L.H. Kauffman, S. Lins. Decomposition of the vertex group of
   $3$-manifolds. {\it Discrete Math.} 103 (1992), no. 1, 49--55.
   
 \item L.H. Kauffman, S. Lins.  Computing Turaev-Viro invariants for
   $3$-manifolds. {\it Manuscripta Math.} 72 (1991), no. 1, 81--94.
   
 \item H. Everett, C. M.H. de Figueiredo, C. Linhares-Sales, F. Maffray. O.
   Porto, B. Reed.  Even pairs. Perfect graphs, 67--92, Wiley-Intersci. Ser.
   {\it Discrete Math. Optim.}, Wiley, Chichester, 2001.
   
 \item C. Linhares-Sales, F. Maffray, B.  Reed. Recognizing planar strict
   quasi-parity graphs. {\it Graphs Combin.} 17 (2001), no. 4, 745--757.
 
 \item C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, B. Reed. Finding skew
   partitions efficiently.  {\it J. Algorithms} 37 (2000), no. 2, 505--521.
 
 \item G. Calinescu, C.G. Fernandes, B. Reed. Multicuts in unweighted graphs
   with bounded degree and bounded tree-width.  Integer programming and
   combinatorial optimization (Houston, TX, 1998), 137--152, {\it Lecture
     Notes in Comput. Sci.}, 1412, Springer, Berlin, 1998.  Aceito no J.
   Algorithms.
   
 \item H. Everett, S. Klein, B. Reed. An optimal algorithm for finding
   clique-cross partitions. Proceedings of the Twenty-ninth Southeastern
   International Conference on Combinatorics, Graph Theory and Computing (Boca
   Raton, FL, 1998). {\it Congr. Numer.} 135 (1998), 171--177.
 
 \item C. Linhares-Sales, F. Frédéric and B. Reed. On planar perfectly
   contractile graphs. {\it Graphs Combin.} 13 (1997), no. 2, 167--187.
 
\item H. Everett,  C. M. H. de Figueiredo, C.  Linhares-Sales,
  F. Maffray, O. Porto, B. Reed. Path parity and perfection.  Graphs and
  combinatorics (Marseille, 1995). {\it Discrete Math.} 165/166 (1997),
  233--252.
 
\item H. Everett, S. Klein and B. Reed.  An algorithm for finding homogeneous
  pairs. {\it Discrete Appl. Math.} 72 (1997), no. 3, 209--218.
  
  
\item B. Reed and C. Linhares-Sales (eds). {\it Recent advances in algorithms
  and combinatorics.} CMS Books in Mathematics/Ouvrages de Mathématiques de la
  SMC, 11. Springer-Verlag, New York, 2003. xiv+351 pp. ISBN: 0-387-95434-1
  05-06

\item Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi.
  Multidimensional Cube Packing. GRACO'2001: Brazilian Symposium on Graphs and
  Combinatorics. {\it Electronic Notes of Discrete Mathematics} (Elsevier
  Science).

\item Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi,
 Multidimensional Cube Packing, 2002. Submetido.
 
\item M.-F. Sagot and Y. Wakabayashi, Pattern inference under many guises.
  {\it Recent advances in algorithms and combinatorics,} 245--287, CMS Books
  Math./Ouvrages Math. SMC, 11, Springer, New York, 2003. 
%  \texttt{(http://www.springer.de/search97cgi/s97\_cgi)}

\item E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, Some Approximation
  Results for the Maximum Agreement Forest Problem. Proc. of
  APPROX-RANDOM 2001 (Approximation, Randomization, and Combinatorial
  Optimization: Algorithms and Techniques), M. Goemans et al (Eds.), {\it
    Lecture Notes in Computer Science}, vol. 2129, Springer (2001), 159-169.

\item E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest
  Problem: Approximation algorithms and computational experiments. Submetido.
  
\item M. Grötschel, C. Thomassen and Y. Wakabayashi, Hypotraceable Digraphs,
  {\it Journal of Graph Theory} 4 (1980) 377-381.

  
\item M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty. Matching covered graphs
  and subdivisions of $K\sb 4$ and $\overline C\sb 6$. {\it J. Combin. Theory Ser.
  B} 66 (1996), no. 2, 263--268. 
 
\item M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Ear decompositions of
  matching covered graphs, {\it Combinatorica}, 19 (2) (1999), 151-174. 

\item  M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, On a conjecture of
  Lovász concerning bricks I: The characteristic of a matching covered graph,
  {\it Journal of Combinatorial Theory (B)}, 85 (1) (2002), 94-136.

\item  M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, On a conjecture of
  Lovász concerning bricks II: Bricks of Finite Characteristic, {\it Journal of
  Combinatorial Theory (B)}, 85 (1) (2002), 137-180.
  
\item M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Optimal ear
  decompositions of matching covered graphs and bases for the matching
  lattice, {\it Journal of Combinatorial Theory (B)}, 85 (1) (2002), 59-93.
  
\item M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty. The matching
  lattice.  {\it Recent advances in algorithms and combinatorics,}
  1--25, CMS Books Math./Ouvrages Math. SMC, 11, Springer, New York,
  2003.
  
\end{enumerate}
\end{document}</pre></body></html>