Friday March 16, 2001

16:00-17:30

Registration

16:30-21:30

Symposium & CIMPA School Barbecue


 
 

Saturday March 17, 2001

8:30-9:00

Opening Session

9:00-9:50

Invited Talk:
The FISH Machine at Bletchley Park
William Tutte 

9:50-10:20

Coffee-break

 

Graph Theory

Approximation Algorithms

10:20-10:50

(#077) S. Ceroi, F. Havet
Trees with three leaves are (n+1)-unavoidable

(#074) G. Calinescu, C. Fernandes
Multicuts in Unweighted digraphs with Bounded Degree and Bounded Tree-Width 

10:50-11:20

(#014) F. Fomin, M. Matamala, E. Prisner, I. Rapaport
Bilateral Orientation and Domination 

(#045) F. Miyazawa, Y. Kohayakawa, P. Raghavan, Y. Wakabayashi 
Multidimensional Cube Packing 

11:20-11:50

(#019) A. Morgana, C. Mello, G. Sontacchi
An algorithm for 1-bend embeddings of planar graphs in the Two-dimensional Grid

(#061) M. Dawande, J. Kalagnanam, J. Sethuraman 
Variable Sized Bin Packing With Color Constraints

11:50-12:20

(#046) C. Silva, R. Dahab 
Tutte's 3-flow Conjecture and Matchings in Bipartite Graphs

(#021) A. Baltz, T. Schoen, A. Srivastav 
Probabilistic Analysis of Bipartite Traveling Salesman Problems

12:20-14:00

Lunch

14:00-14:50

Invited Talk:
List Colouring Via the Probabilisitc Method
Bruce Reed

 

Cartesian Products

Combinatorial Biology

15:00-15:30

(#043) T. Hasunuma 
Independent Spanning Cycle-Rooted Trees  in the Cartesian Product of Digraphs

(#023) J. Jansson 
On the Complexity of Inferring Rooted Evolutionary Trees 

15:30-16:00

(#022) A. Anta, T. Leighton, J. Presa 
Containment Properties of
Product and Power Graphs 

(#062) S. Adi, C. Ferreira 
DNA Fragments Assembly Programs: a Comparative Study

16:00-16:30

Coffee-break

 

Combinatorial Designs

Combinatorial Optimization

16:30-17:00

(#026) V. Grolmusz 
Constructive upper bound for intersecting set systems 

(#063) J. Lage, R. Assunção, E. Reis 
A Minimal Spanning Tree  Algorithm Applied to Spatial Cluster Analysis

17:00-17:30

(#034) J. Kim 
Nearly Optimal Partial Steiner Systems 

(#060) M. Aragão, E. Uchoa, R. Werneck 
Dual heuristics on the exact solution  of Large Steiner Problems

17:30-18:00

(#030) C. Moreira, Y. Kohayakawa 
Bounds for optimal coverings 

(#042) M. Campêlo, C. Bornstein 
ADD/DROP Procedures for the Capacitated  Plant Location Problem


 
 

Sunday March 18, 2001

8:30-9:20

Invited Talk:
Shortest paths, resistance, and the energy of convex sets
László Lovász

 

Clique Graphs I

Network Flows

9:30-10:00

(#010) F. Larrión, V. Neumann-Lara, M. Pizaña 
Clique Divergent Clockwork Graphs  and Partial Orders

(#036) J. Cohen 
A Graph Partitioning Scheme and Applications  to Fault Tolerant Computing

10:00-10:30

(#040) M. Gutierrez, J. Meidanis 
The Clique Operator, Set Families,  and Their Properties

(#032) C. Bornstein, A. Ribeiro, A. Lucena 
Maximizing flow under Special Nonnegative Lower Bounds on Arc Flows  

10:30-11:00

Coffee-break

 

Integer Programming

Data Structures

11:00-11:30

(#069) I. Díaz, P. Zabala

A Polyhedral Approach for Graph Coloring

(#059) P. Poblete, A. Viola

The Effect of Deletions on Different Insertion Disciplines for Hash Tables

11:30-12:00

(#057) L. Motta, L. Ochi, C. Martinhon

Reduction Rules for the Covering Tour Problem

(#039) E. Laber, L. Nogueira

Fast Searching in Trees

12:00-12:30

(#033) A. Lucena, M. Resende

Generating Lower Bounds for the Prize Collecting Steiner Problem
in Graphs

(#018) L. Lins, S. Lins, S. Melo

Symmetry Robust Memory Management of Multidimensional Arrays

12:30-14:00

Lunch

14:00-14:50

Invited Talk:
Square-Free Perfect Graphs
Gérard Cornuéjols

 

Perfect Graphs

Scheduling

15:00-15:30

(#073) R. Hayward, W. Lenhart

Perfectly Orderable P4 Composition

(#054) M. Dawande, S. Kumar, C. Sriskandarajah

Scheduling Advertisements on a Web Page: New and Improved Approximation Algorithms

15:30-16:00

(#072) R. Sampaio, C. Sales

On the Complexity of Finding Even Pairs in Planar Perfect Graphs

(#070) A. Goldman, C. Rapine

Scheduling with Duplication on m Processors with Small Communication Delays

16:00-16:30

(#041) P. Hell, S. Klein, F. Protti, L. Nogueira

On Generalized Split Graphs

(#064) M. Campêlo, R. Corrêa, N. Maculan, F. Protti

ILP Formulations for Scheduling Ordered Tasks on a Bounded Number of Processors

16:30-17:00

Coffee-break

17:00-17:50

Invited Talk:
The Sylvester-Gallai Theorem and Metric Spaces
Vasek Chvátal


 
 

Monday March 19, 2001

8:30-9:20

Invited Talk:
The Triangles in Graphs and Directed graphs
Adrian Bondy

 

Graph Approximation Algorithms

Distributed Algorithms

9:30-10:00

(#012) L. Faria, C. Figueiredo, C. Mendonça

On the Complexity of the Approximation of Nonplanarity Parameters for Cubic Graphs

(#009) E. Laber, L. Holanda

On Asymmetric Communication Protocols

10:00-10:30

(#035) B. Doerr, A. Srivastav

Multi-Color Discrepancies

(#053) L. Penso, V. Barbosa

A Distributed Algorithm for k-dominating Sets

10:30-11:00

Coffee-break

 

Clique Graphs II

Discrete Algorithms

11:00-11:30

(#008) M. Pizaña

Distances and Diameters on Iterated Clique Graphs

(#055) A. Sa, P. Carvalho

Color Quantization by Pairwise Clustering Using a Reduced Graph

11:30-12:00

(#052) L. Alcón, M. Gutierrez

Clique Planar Graphs

(#011) V. Dias, G. Fonseca, C. Figueiredo, J. Szwarcfiter

Stable Marriages with Restricted Pairs

12:00-12:30

(#068) A. Bondy, G. Durán, M. Lin, J. Szwarcfiter

A Sufficient Condition for Self-Clique Graphs

(#038) D. Jacobs, C. Machado, V. Trevisan

An O(n2) Algorithm  for the Characteristic Polynomial of a Tree

12:30-14:00

Lunch

14:00-14:50

Invited Talk:
Tries and Concentration
Luc Devroye

 

Graph Colourings

Enumerative Combinatorics

15:00-15:30

(#076) M. Valencia-Pabon

Revisiting Tucker's Algorithm to Color Circular-Arc Graphs

(#017) Z. Gao, J. Wang

Exact Enumeration of Rooted 3-connected Triangular Maps
 on the Projective Plane

15:30-16:00

(#013) S. Dantas, S. Gravier, F. Maffray, B. Mohar

Extremal Graphs for the List-Coloring Version of a Theorem of Nordhaus and Gaddum

(#049) B. Uchôa, C. Pimentel

Enumerative Combinatorics and Shannon's Theory of Discrete Noiseless Channels

16:00-16:30

(#067) V. Vu

Some Recent Results on List Coloring

(#051) F. Müller, M. Camozzato, O. Araújo

Exact Algorithms for the Imbalanced Time Minimizing Assignment Problem

16:30-17:00

(#028) V. Ravelomanana, L. Thimonier

Asymptotic Enumeration of Cographs


 
 

Tuesday March 20, 2001

14:00

Excursion

20:00

Symposium & CIMPA School Dinner