Program

	Tuesday April 26	Wednesday April 27		Thursday April 28		Friday April 29
07:50 – 08:20		Registration
08:20 – 08:30		Opening
08:30 – 09:30		Invited talk 1 C. Thomassen		Invited talk 3 P. Hell		Invited talk 5 B. Reed
09:30 – 09:50		GT1	CO1	GA1	PC2	PGr	Pck
09:55 – 10:15		GT1	CO1	GA1	PC2	PGr	Pck
10:20 – 10:40		GT1	CO1	GA1	PC2	PGr	Pck
10:40 – 11:00		coffee break		coffee break		coffee break
11:00 – 11:20		GT2	RAl	GA2	ECM	NFl	CO2
11:25 – 11:45		GT2	RAl	GA2	ECM	NFl	CO2
11:50 – 12:10		GT2	RAl	Invited talk 4 M. Grötschel		NFl
12:10 – 12:50		LUNCH				LUNCH
13:00 – 14:00				Excursion (sailing tour and lunch)
14:00 – 14:20		GT3	CpC			GT4	ADS
14:25 – 14:45		GT3	CpC			GT4	ADS
14:50 – 15:10		GT3	CpC			GT4	ADS
15:10 – 15:30		coffee break				coffee break
15:30 – 16:30		Invited talk 2 Y. Kohayakawa				Invited talk 6 R. Karp
16:30 – 16:50		GCl	PC1			Closing
16:55 – 17:15	Registration	GCl	PC1
17:20 – 17:40		GCl	PC1
19:00 – 20:00	Welcome cocktail	Special Session
20:00 – 22:00	DINNER	BARBECUE DINNER		DINNER
21:00 – 22:00	Registration

List of Invited Talks

Invited talk 1   (Wednesday 8:30 – 9:30)

Chair: Cristina Gomes Fernandes

• On the number of colorings of a graph
  Carsten Thomassen

Invited talk 2   (Wednesday 15:30 – 16:30)

Chair: Eduardo Sany Laber

• On a theorem of Luczak
  Yoshiharu Kohayakawa

Invited talk 3   (Thursday 8:30 – 9:30)

Chair: Sulamita Klein

• From colouring to constraint satisfaction
  Pavol Hell

Invited talk 4   (Thursday 11:50 – 12:50)

Chair: Yoshiko Wakabayashi

• Telecommunication, graphs, and combinatorial optimization
  Martin Grötschel

Invited talk 5   (Friday 8:30 – 9:30)

Chair: Celina M. H. Figueiredo

• Packings and coverings of odd cycles
  Bruce Reed

Invited talk 6   (Friday 15:30 – 16:30)

Chair: Arnaldo Mandel

• Fair bandwidth allocation
  Richard Karp

Special Session  to celebrate the 60th birthday of Cláudio L. Lucchesi   (Wednesday 19:00 – 20:00)

Chair: Jayme Szwarcfiter

• Our association with Claudio Lucchesi
  U. S. R. Murty and Marcelo H. de Carvalho

List of Parallel Sessions

(The presenter/speaker is underlined.)

(ADS)  Algorithms and Data Structures   (Friday 14:00 – 15:10)

Chair: Ricardo Corrêa

1. Building PQR trees in almost-linear time
   Guilherme P. Telles, João Meidanis
2. An all-substrings common subsequence algorithm
   C. E. R. Alves, E. N. Cáceres, S. W. Song
3. Alignment with non-overlapping inversions in O(n³ log n) time
   Carlos E. R. Alves, Alair Pereira do Lago, Augusto F. Vellozo

(CO1)  Combinatorial Optimizaton I   (Wednesday 9:30 – 10:40)

Chair: Eduardo Uchoa

1. A multistart constructive heuristic for sequencing by hybridization using adaptive memory
   Eraldo R. Fernandes, Celso C. Ribeiro
2. A Gray code for binary subtraction
   Joe Sawada
3. Faster algorithms for feedback vertex set
   Venkatesh Raman, Saket Saurabh, C. R. Subramanian NO-SHOW

(CO2)  Combinatorial Optimization II   (Friday 11:00 – 11:45)

Chair: Orlando Lee

1. Computing the integrality gap of the asymmetric travelling salesman problem
   Sylvia Boyd, Paul Elliott-Magwood
2. Advances in packing directed joins
   Aaron M. Williams, Bertrand Guenin
3. Search locally to arrange cyclically
   Murali K. Ganapathy, Sachin P. Lodha CANCELLED

(CpC)  Complexity / Coloring   (Wednesday 14:00 – 15:10)

Chair: Luerbio Faria

1. On the computational complexity of partial covers of Theta graphs
   Jiří Fiala, Jan Kratochvíl, Attila Pór
2. Between coloring and list-coloring: \mu-coloring
   Flavia Bonomo, Mariano Cecowski
3. Upper bound on the non-colorability threshold of the 2+p-COL problem
   Roberto Cruz

(ECM)  Enumerative Combinatorics / Matroids   (Thursday 11:00 – 11:45)

Chair: Arnaldo Mandel

1. Non-separating cocircuits in matroids
   Manoel Lemos, T. R. B. Melo
2. The distribution of the path edge-covering numbers for random trees
   Alois Panholzer

(GA1)  Graph Algorithms I   (Thursday 9:30 – 10:40)

Chair: Zoltán Szigeti

1. A new refinement procedure for graph isomorphism algorithms
   Mateus de Oliveira Oliveira, Fabíola Greve
2. Planar graph bipartization in linear time
   Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta
3. (p,k)-colorings in line graphs
   Marc Demange, Tinaz Ekim, Dominique de Werra

(GA2)  Graph Algorithms II   (Thursday 11:00 – 11:45)

Chair: Claudson Bornstein

1. Probe interval bigraphs
   Gerard Jennhwa Chang, Ton Kloks, Sheng-Lung Peng
2. Generating all the cubic graphs that have a 6-cycle double cover
   Rodrigo S. C. Leão, Valmir C. Barbosa

(GCl)  Graph Colouring   (Wednesday 16:30 – 17:40)

Chair: Yoshiharu Kohayakawa

1. Improved bounds on acyclic edge colouring
   Rahul Muthu, Narayanan N., C. R. Subramanian NO-SHOW
2. Globally bounded local edge colourings of hypergraphs
   Mathias Schacht, Anusch Taraz
3. Fractionally total colouring G(n,p)
   Conor Meagher, Bruce Reed

(GT1)  Graph Theory I   (Wednesday 9:30 – 10:40)

Chair: Cláudio Lucchesi

1. On the local splitting theorem
   Zoltán Szigeti
2. On bags and bugs
   Pierre Hansen, Dragan Stevanović
3. Searching for geodetic boundary vertex sets
   J. Cáceres, M. L. Puertas, C. Hernando, M. Mora, I. M. Pelayo, C. Seara

(GT2)  Graph Theory II   (Wednesday 11:00 – 12:10)

Chair: Marcelo H. de Carvalho

1. A forbidden subgraph characterization of path graphs
   Silvia B. Tondato, Marisa Gutierrez, Jayme L. Szwarcfiter
2. Forbidden subgraph characterization of split graphs that are UEH
   M. R. Cerioli, P. Petito
3. Non loop graphs with induced cycles
   Liliana Alcón, Márcia R. Cerioli, Celina M. H. de Figueiredo, Marisa Gutierrez, João Meidanis

(GT3)  Graph Theory III   (Wednesday 14:00 – 15:10)

Chair: Célia P. de Mello

1. Local cutpoints and iterated clique graphs
   M. E. Frías-Armenta, F. Larrión, V. Neumann-Lara, M. A. Pizaña
2. A new family of K-divergent graphs
   Martín Matamala, José Zamora
3. On the Hadwiger number of hypercubes and its generalizations
   L. Sunil Chandran, Naveen Sivadasan NO-SHOW

(GT4)  Graph Theory IV   (Friday 14:00 – 15:10)

Chair: Loana Tito Nogueira

1. Degree constrained subgraphs
   L. Addario-Berry, K. Dalal, B. A. Reed
2. On hereditary Helly self-clique graphs
   F. Larrión, M. A. Pizaña
3. The Helly property on subhypergraphs
   Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter

(NFl)  Network Flows   (Friday 11:00 – 12:10)

Chair: Edson Cáceres

1. Detecting flows congesting a target network link
   D. Barth, P. Berthomé, M. Diallo
2. A general approach to L(h,k)-label interconnection networks
   Tiziana Calamoneri, Saverio Caminiti, Rossella Petreschi
3. Optimal flow distribution among multiple channels with unknown capacities
   Richard Karp, Till Nierhoff, Till Tantau

(PC1)  Polyhedral Combinatorics I   (Wednesday 16:30 – 17:40)

Chair: Manoel Campêlo / Irene Loiseau / André Guedes

1. The combinatorial stages of chromatic scheduling polytopes
   Javier Marenco, Annegret Wagler
2. On the asymmetric representatives formulation for the vertex coloring problem
   Manoel Campêlo, Victor Campos, Ricardo Corrêa
3. Stabilized branch-and-cut-and-price for the generalized assignment problem
   Alexandre Pigatti, Marcus Poggi de Aragão, Eduardo Uchoa

(PC2)  Polyhedral Combinatorics II   (Thursday 9:30 – 10:40)

Chair: Marcus Poggi de Aragão

1. The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
   Mourad Baïou, José R. Correa
2. Algorithms for the degree-constrained minimum spanning tree problem
   Alexandre Salles da Cunha, Abilio Lucena CANCELLED
3. Lehman's equation on near-ideal clutters
   G. Argiroffo, S. Bianchi, G. Nasini

(Pck)  Packing Problems   (Friday 9:30 – 10:40)

Chair: José Correa

1. Two- and three-dimensional parametric packing
   F. K. Miyazawa, Y. Wakabayashi
2. Two aspects of the pallet loading problem
   Walter F. Mascarenhas
3. A one-dimensional bin packing problem with shelf divisions
   E. C. Xavier, F. K. Miyazawa

(PGr)  Perfect Graphs   (Friday 9:30 – 10:40)

Chair: Kristina Vuskovic

1. Perfect subgraph/supergraph
   Murilo V. G. da Silva, André L. P. Guedes
2. Three classes of minimal circular-imperfect graphs
   Arnaud Pêcher, Annegret K. Wagler, Xuding Zhu
3. Partial characterizations of clique-perfect graphs
   Flavia Bonomo, Maria Chudnovsky, Guillermo Durán

(RAl)  Randomized Algorithms   (Wednesday 11:00 – 12:10)

Chair: Bruce Reed

1. Randomized mechanisms for limited supply multi-item auctions
   Claudson F. Bornstein, Eduardo Sany Laber, Marcelo A. F. Más
2. Large k-independent sets of random regular graphs
   Mihalis Beis, William Duckworth, Michele Zito CANCELLED
3. On some applications of randomized memory
   Vince Grolmusz