GRACO 2005




April 26
April 27
April 28
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 GT1CO1 GA1PC2 PGrPck
09:55 – 10:15 GT1CO1 GA1PC2 PGrPck
10:20 – 10:40 GT1CO1 GA1PC2 PGrPck
10:40 – 11:00 coffee break coffee break coffee break
11:00 – 11:20 GT2RAl GA2ECM NFlCO2
11:25 – 11:45 GT2RAl GA2ECM NFlCO2
11:50 – 12:10 GT2RAl Invited talk 4
M. Grötschel
12:10 – 12:50 LUNCH LUNCH
13:00 – 14:00 Excursion
(sailing tour
and lunch
14:00 – 14:20 GT3CpC GT4ADS
14:25 – 14:45 GT3CpC GT4ADS
14:50 – 15:10 GT3CpC GT4ADS
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 GClPC1 Closing
16:55 – 17:15 Registration GClPC1  
17:20 – 17:40 GClPC1
19:00 – 20:00 Welcome
Special Session  
20:00 – 22:00   DINNER   BARBECUE
21:00 – 22:00 Registration      


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
  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
(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
(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
  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
(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
  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
  3. On some applications of randomized memory
    Vince Grolmusz

NOTE: The results of the paper The 3-colored 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.


URL of this site:
Last modified: Thu Oct 8 07:29:48 BRT 2009