

Program
List of Invited Talks
 Invited talk 1 (Wednesday 8:30 – 9:30)
 Chair: Cristina Gomes Fernandes
 Invited talk 2 (Wednesday 15:30 – 16:30)
 Chair: Eduardo Sany Laber
 Invited talk 3 (Thursday 8:30 – 9:30)
 Chair: Sulamita Klein
 Invited talk 4 (Thursday 11:50 – 12:50)
 Chair: Yoshiko Wakabayashi
 Invited talk 5 (Friday 8:30 – 9:30)
 Chair: Celina M. H. Figueiredo
 Invited talk 6 (Friday 15:30 – 16:30)
 Chair: Arnaldo Mandel
 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

Building PQR trees in almostlinear time
Guilherme P. Telles,
João Meidanis

An allsubstrings common subsequence algorithm
C. E. R. Alves,
E. N. Cáceres,
S. W. Song

Alignment with nonoverlapping 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

A multistart constructive heuristic for sequencing by hybridization using adaptive memory
Eraldo R. Fernandes,
Celso C. Ribeiro

A Gray code for binary subtraction
Joe Sawada

Faster algorithms for feedback vertex set
Venkatesh Raman,
Saket Saurabh,
C. R. Subramanian
NOSHOW
 (CO2) Combinatorial Optimization II (Friday 11:00 – 11:45)
 Chair: Orlando Lee

Computing the integrality gap of the asymmetric travelling salesman problem
Sylvia Boyd,
Paul ElliottMagwood

Advances in packing directed joins
Aaron M. Williams,
Bertrand Guenin

Search locally to arrange cyclically
Murali K. Ganapathy,
Sachin P. Lodha
CANCELLED
 (CpC) Complexity / Coloring (Wednesday 14:00 – 15:10)
 Chair: Luerbio Faria

On the computational complexity of partial covers of Theta graphs
Jiří Fiala,
Jan Kratochvíl,
Attila Pór

Between coloring and listcoloring: \mucoloring
Flavia Bonomo,
Mariano Cecowski

Upper bound on the noncolorability threshold of the 2+pCOL problem
Roberto Cruz
 (ECM) Enumerative Combinatorics / Matroids (Thursday 11:00 – 11:45)
 Chair: Arnaldo Mandel

Nonseparating cocircuits in matroids
Manoel Lemos,
T. R. B. Melo

The distribution of the path edgecovering numbers for random trees
Alois Panholzer
 (GA1) Graph Algorithms I (Thursday 9:30 – 10:40)
 Chair: Zoltán Szigeti

A new refinement procedure for graph isomorphism algorithms
Mateus de Oliveira Oliveira,
Fabíola Greve

Planar graph bipartization in linear time
Samuel Fiorini,
Nadia Hardy,
Bruce Reed,
Adrian Vetta

(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

Probe interval bigraphs
Gerard Jennhwa Chang,
Ton Kloks,
ShengLung Peng

Generating all the cubic graphs that have a 6cycle double cover
Rodrigo S. C. Leão,
Valmir C. Barbosa
 (GCl) Graph Colouring (Wednesday 16:30 – 17:40)
 Chair: Yoshiharu Kohayakawa

Improved bounds on acyclic edge colouring
Rahul Muthu,
Narayanan N.,
C. R. Subramanian
NOSHOW

Globally bounded local edge colourings of hypergraphs
Mathias Schacht,
Anusch Taraz

Fractionally total colouring G(n,p)
Conor Meagher,
Bruce Reed
 (GT1) Graph Theory I (Wednesday 9:30 – 10:40)
 Chair: Cláudio Lucchesi

On the local splitting theorem
Zoltán Szigeti

On bags and bugs
Pierre Hansen,
Dragan Stevanović

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

A forbidden subgraph characterization of path graphs
Silvia B. Tondato,
Marisa Gutierrez,
Jayme L. Szwarcfiter

Forbidden subgraph characterization of split graphs that are UEH
M. R. Cerioli,
P. Petito

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

Local cutpoints and iterated clique graphs
M. E. FríasArmenta,
F. Larrión,
V. NeumannLara,
M. A. Pizaña

A new family of Kdivergent graphs
Martín Matamala,
José Zamora

On the Hadwiger number of hypercubes and its generalizations
L. Sunil Chandran,
Naveen Sivadasan
NOSHOW
 (GT4) Graph Theory IV (Friday 14:00 – 15:10)
 Chair: Loana Tito Nogueira

Degree constrained subgraphs
L. AddarioBerry,
K. Dalal,
B. A. Reed

On hereditary Helly selfclique graphs
F. Larrión,
M. A. Pizaña

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

Detecting flows congesting a target network link
D. Barth,
P. Berthomé,
M. Diallo

A general approach to L(h,k)label interconnection networks
Tiziana Calamoneri,
Saverio Caminiti,
Rossella Petreschi

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

The combinatorial stages of chromatic scheduling polytopes
Javier Marenco,
Annegret Wagler

On the asymmetric representatives formulation for the vertex coloring problem
Manoel Campêlo,
Victor Campos,
Ricardo Corrêa

Stabilized branchandcutandprice 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

The nodeedge weighted 2edge connected subgraph problem: linear relaxation, facets and separation
Mourad Baïou,
José R. Correa

Algorithms for the degreeconstrained minimum spanning tree problem
Alexandre Salles da Cunha,
Abilio Lucena
CANCELLED

Lehman's equation on nearideal clutters
G. Argiroffo,
S. Bianchi,
G. Nasini
 (Pck) Packing Problems (Friday 9:30 – 10:40)
 Chair: José Correa

Two and threedimensional parametric packing
F. K. Miyazawa,
Y. Wakabayashi

Two aspects of the pallet loading problem
Walter F. Mascarenhas

A onedimensional bin packing problem with shelf divisions
E. C. Xavier,
F. K. Miyazawa
 (PGr) Perfect Graphs (Friday 9:30 – 10:40)
 Chair: Kristina Vuskovic

Perfect subgraph/supergraph
Murilo V. G. da Silva,
André L. P. Guedes

Three classes of minimal circularimperfect graphs
Arnaud Pêcher,
Annegret K. Wagler,
Xuding Zhu

Partial characterizations of cliqueperfect graphs
Flavia Bonomo,
Maria Chudnovsky,
Guillermo Durán
 (RAl) Randomized Algorithms (Wednesday 11:00 – 12:10)
 Chair: Bruce Reed

Randomized mechanisms for limited supply multiitem auctions
Claudson F. Bornstein,
Eduardo Sany Laber,
Marcelo A. F. Más

Large kindependent sets of random regular graphs
Mihalis Beis,
William Duckworth,
Michele Zito
CANCELLED

On some applications of randomized memory
Vince Grolmusz
NOTE:
The results of the paper
The 3colored Ramsey number of odd cycles,
by Y. Kohayakawa, M. Simonovits and J. Skokan,
will be covered in the talk
On a theorem of Luczak,
to be delivered by Y. Kohayakawa.
