LAGOS'07 Preliminary Program
Place: 25-29 November 2007, Hotel Cabañas del Lago, Puerto Varas,
Chile
[view as a table]
[pdf version]
Sunday, 25th.
15:00 - 19:00: Registration (Hotel Cabañas del Lago)
19:00: Cocktail (Hotel Cabañas del Lago)
Monday, 26th
8:45-9:00 Opening Session (Petrohue Room)
09:00: Plenary Talk A (Petrohue Room)
Chair: Martín Matamala
09:00 - 09:50 l
Laurence Wolsey (CORE-UCL, Belgium)
"Simple Mixed Integer Sets: Polyhedra and Algorithms"
Room Petrohue:
10:00 a 10:40: Structural Characterizations of Graphs I
- Chair: Luciano Grippo
10:00:10:20:"Partial Characterizations of Circular-Arc Graphs"
Flavia Bonomo (CONICET and UBA, Argentina),
Guillermo Alfredo Durán (U Chile, Chile -
UBA, Argentina), Luciano Norberto Grippo (CONICET
and UBA, Argentina) and Martín Darío Safe (CONICET
and UBA, Argentina)
10:20-10:40:"Sufficient conditions for a graph to be edge-colorable
with maximum degree colors"
Raphael Machado (UFRJ, Brazil) and
Celina de Figueiredo (UFRJ, Brazil)
Room Calbuco:
10:00 a 11:00: Combinatorial Optimization I - Chair: Gelasio
Salazar
10:00:10:20: "A New Neighborhood for the QAP"
Elizabeth Goldbarg (UFRN, Brazil),
Nelson Maculan (UFRJ, Brazil) and Marco
Goldbarg (UFRN, Brazil)
10:20:10:40: "A central approach to bound the number of crossings
in a generalized configuration"
Silvia Fernández-Merchant (California State
U, USA), Bernardo M. Ábrego (California
State U, USA), Jesús Leaños (U Autónoma
de San Luis Potosí, México) and Gelasio Salazar (U
Autónoma de San Luis Potosí, México)
10:40-11:00: "Repetition-free longest common subsequence"
Said Adi (UFMS, Brazil), Marília Braga
(U Lyon I, France), Cristina Fernandes
(USP, Brazil), Carlos Ferreira (USP,
Brazil), Fábio Martinez (UFMS, Brazil),
Marie-France Sagot (U Lyon I, France),
Marco Stefanes (UFMS, Brazil), Christian
Tjandraatmadja (USP, Brazil) and Yoshiko
Wakabayashi (USP, Brazil)
11:00-11:30: Coffee-Break
11:30: Plenary Talk B (Room Petrohue)
Chair: Maria Chudnovsky
11:30 - 12::20 l Robin
Thomas (Georgia Institute of Technology,
USA)
"Coloring triangle-free graphs on surfaces"
Room Petrohue:
12:30 a 13:10: Colorings of Graphs I - Chair: Mario Valencia-Pabon
12:30:12:50: "Totally multicolored diamonds"
Juan Jose Montellano (UNAM, Mexico)
12:50:13:10: "Chromatic Edge Strength of Some Multigraphs"
Jean Cardinal (CSD, U Libre de Bruxelles,
Belgium), Vlady Ravelomanana (LIPN,
U Paris-Nord, France) and Mario Valencia-Pabon (LIPN,
U Paris-Nord, France)
Room Calbuco:
12:30 a 13:10: Computational Complexity I - Chair: Luerbio
Faria
12:30-12:50: "On the complexity of feedback set problems in signed
digraphs"
Marco Montalva (U Chile, Chile), Julio
Aracena (U Chile, Chile) and Anahi
Gajardo (U Chile, Chile)
12:50-13:10: "2K_2 vertex-set partition into nonempty parts"
Simone Dantas (IM, UFF, Brazil), Elaine
Eschen (Lane Department of CS and EE, USA),
Luerbio Faria (FFP, UERJ, Brazil),
Celina M. H. de Figueiredo (COPPE, UFRJ, Brazil)
and Sulamita Klein (IM and COPPE, UFRJ, Brazil)
13:10-14:30: Lunch
14:30: Plenary Talk C (Room Petrohue)
Chair: José Correa
14:30 - 15:20 l Ken-ichi
Kawarabayashi (Tohoku University, Japan)
"List-coloring graphs on a fixed surface and minor-closed class
of graphs"
Room Petrohue:
15:30-16:30: Clique graphs I- Chair: Liliana Alcon
15:30-15:50: "On cliques of Helly Circular-arc Graphs"
Min Chih Lin (UBA, Argentina), Ross
McConnell (Colorado State U, USA),
Francisco Soulignac (UBA, Argentina)
and Jayme Szwarcfiter (UFRJ, Brazil)
15:50-16:10: "On maximizing clique, clique-Helly and hereditary
clique-Helly induced subgraphs"
Liliana Alcon (UNLP, Argentina), Luerbio
Faria (UERJ, Brazil), Celina M. H.
de Figueiredo (UFRJ, Brazil) and Marisa
Gutierrez (UNLP, Argentina)
16:10-16:30: "Random Graphs, Retractions and Clique Graphs"
Francisco Larrión (UNAM, Mexico), Miguel
Ángel Pizaña (UAM, Mexico) and Rafael
Villarroel-Flores (UAEH, Mexico)
Room Calbuco:
15:30-16:30: Graph algorithms - Chair: Juan José
Salazar González
15:30-15:50: "A New Lower Bound for the Minimum Linear Arrangement
of a Graph"
André Amaral (UFES, Brazil), Alberto
Caprara (U Bologna, Italy), Adam Letchford
(Lancaster U, England) and Juan José
Salazar González (U de La Laguna, Spain)
15:50-16:10: "A Polynomial Time Algorithm for Recognizing Near-Bipartite
Pfaffian Graphs"
Alberto Alexandre Assis Miranda (IC, UNICAMP,
Brazil) and Cláudio Leonardo Lucchesi (IC,
UNICAMP, Brazil)
16:10-16:30: "The Generalized Max-Controlled Set Problem"
Ivairton M. Santos (UFMT, Brazil),
Carlos A. Martinhon (DCC, IC, UFF, Brazil)
and Luiz S. Ochi (DCC, IC, UFF, Brazil)
16:30-16:50: Coffee-Break
16:50: Plenary Talk D (Room Petrohue)
Chair: Graciela Nasini
16:50 - 17:40 l François
Margot (Carnegie Mellon University, USA)
"On the Football Pool Problem"
Room Petrohue:
17:50-18:50: Intersection Graphs - Chair: Marisa Gutierrez
17:50-18:10: "Linear-Interval Dimension and PI Orders"
Márcia Cerioli (UFRJ, Brazil), Fabiano
Oliveira (UFRJ, Brazil) and Jayme Szwarcfiter
(UFRJ, Brazil)
18:10-18:30: "Clique-coloring UE and UEH graphs"
Márcia Cerioli (UFRJ, Brazil) and Priscila
Petito (UFRJ, Brazil)
18:30-18:50: "Clique trees of chordal graphs: leafage and 3-asteroidal"
Marisa Gutierrez (DM, UNLP, Argentina),
Jayme Szwarcfiter (UFRJ, Brazil) and
Silvia Tondato (DM, UNLP, Argentina)
Room Calbuco:
17:50-18:30: Integer Programming - Chair: Celso Ribeiro
17:50-18:10: "Constraint Programming for the Diameter Constrained
Minimum Spanning Tree Problem"
Thiago Noronha (PUC-Rio, Brazil), Celso
Ribeiro (PUC-Rio, Brazil) and Andrea
Santos (PUC-Rio, Brazil)
18:10-18:30: "Integer Programming Formulations for the k-Cardinality
Tree Problem"
Frederico Quintão (UFMG, Brazil), Alexandre
Cunha (UFMG, Brazil) and Geraldo Mateus
(UFMG, Brazil)
Tuesday, 27th
08:45 - 09:00 l
Jayme L. Szwarcfiter (UFRJ, Brazil)
"To the memory of Peter Hammer (1936-2006)" (Petrohue Room)
Chair: Lawrence Wolsey
09:00: Plenary Talk E (Petrohue Room)
Chair: Guillermo Durán
09:00 - 09:50 l Maria
Chudnovsky (Columbia University, USA)
"Even pairs in Berge graphs"
Room Petrohue:
10:00-11:00: Colorings of Graphs II-Chair: Célia
P. de Mello
10:00-10:20: "Edge Coloring of Split Graphs"
Sheila Almeida (UNICAMP, Brazil), Célia
P. de Mello (UNICAMP, Brazil) and Aurora
Morgana (U Roma "La Sapienza", Italy)
10:20-10:40: "Strong oriented chromatic number: A Steinberg like
problem"
Mickael Montassier (LaBRI, U Bordeaux 1, France),
Pascal Ochem (LaBRI, U Bordeaux 1, France)
and Alexandre Pinlou (LaBRI, U Bordeaux 1,
France):
10:40-11:00: "Colouring clique-hypergraphs of circulant graphs"
Christiane N. Campos (USP, Brazil),
Simone Dantas (UFF, Brazil) and Célia
P. de Mello (UNICAMP, Brazil)
Room Calbuco:
10:00-11:00: Polyhedral Combinatorics - Chair: Javier Marenco
10:00-10:20: "The nonidealness index of circulant matrices"
Gabriela R. Argiroffo (UNR, Argentina)
and Silvia María Bianchi (UNR, Argentina)
10:20-10:40: "Arithmetic relations in the set covering polyhedron
of circulant clutters"
Nestor Aguilera (CONICET and UNL, Argentina)
10:40-11:00: "The football pool polytope"
Javier Marenco (UBA and UNGS, Argentina)
and Pablo Rey (U Chile, Chile)
11:00-11:30: Coffee-Break
11:30: Plenary Talk F (Room Petrohue)
Chair: Jayme Szwarcfiter
11:30 - 12:20 l Yoshiharu
Kohayakawa (USP, Brazil)
"The size-Ramsey number"
12:20: Plenary Talk G (Room Petrohue)
Chair: Pablo Rey
12:20 - 13:10 l Graciela
Nasini (UNR, Argentina)
"From imperfection to nonidealness"
13:10-14:30: Lunch
14:30-19:30: Trip
Wednesday, 28th
09:00: Plenary Talk H (Petrohue Room)
Chair: Annegret Wagler
09:00 - 09:50 l George
Nemhauser (Georgia Institute of Technology,
USA)
"Scheduling On Demand Passenger Air Service"
Room Petrohue:
10:00-11:00: Structural Characterizations of Graphs II -
Chair: Luerbio Faria
10:00-10:20: "Nowhere-zero 5-flows and (1,2)-factors"
Martín Matamala (U Chile, Chile) and
José Zamora (U Chile, Chile)
10:20-10:40: "Flow Critical Graphs"
Cândida Nunes da Silva (IC, UNICAMP, Brazil)
and Cláudio Leonardo Lucchesi (IC, UNICAMP,
Brazil)
10:40-11:00: "Flow Hypergraph Reducibility (Extended Abstract)"
André L. P. Guedes (UFPR, Brazil),
Lilian Markenzon (UFRJ, Brazil) and
Luerbio Faria (UERJ, Brazil)
Room Calbuco:
10:00-11:00: Operations Research - Chair: Héctor
Cancela
10:00-10:20: "Stronger upper and lower bounds for a hard batching
problem to feed assembly lines"
Alexandre Salles da Cunha (UFMG, Brazil)
and Mauricio Cardoso de Souza (UFMG, Brazil)
10:20-10:40: "A robust P2P streaming architecture and its application
to a high quality live-video service"
Pablo Rodriguez-Bocca (IRISA/INRIA, France),
Héctor Cancela (IC, U República, Uruguay),
Franco Robledo Amoza (IC, U República, Uruguay),
Gerardo Rubino (IRISA/INRIA, France)
and Ariel Sabiguero (IRISA/INRIA, France)
10:40-11:00: "A priori and a posteriori aggregation procedures
to reduce model size in MIP mine planning models"
Andres Weintraub (U Chile, Chile),
Marianela Pereira (U Chile, Chile)
and Ximena Schultz (U Chile, Chile)
11:00-11:30: Coffee-Break
11:30: Plenary Talk I (Room Petrohue)
Chair: Marcos Kiwi
11:30 - 12:20 l Fedor
Fomin (University of Bergen, Norway)
"Subexponential parameterized algorithms"
Room Petrohue:
12:30-13:10: Clique Graphs II - Chair: Francisco Larrión
12:30-12:50: "Iterated Clique Graphs and Contractibility (Extended
Abstract)"
Francisco Larrión (UNAM, Mexico), Miguel
Ángel Pizaña (UAM, Mexico) and Rafael
Villarroel-Flores (UAEH, Mexico)
12:50-13:10: "G-Graphs and Algebraic Hypergraphs"
Alain Bretto (DCS, U Caen, France),
Cerasela Jaulin (DCS, U Caen, France),
Kevin G. Kirby (DCS, Northern Kentucky U,
USA) and Bernard Laget (ENISE, France)
Room Calbuco:
12:30-13:10: Coverings and Packings - Chair: Douglas Rall
12:30-12:50: "Limited Packings in Graphs"
Robert Gallant (Memorial U of Newfoundland,
Canada), Georg Gunther (Memorial U
of Newfoundland, Canada), Bert Hartnell (Saint
Mary's U, Canada) and Douglas Rall (Furman
U, USA)
12:50-13:10: "On the Packing Chromatic Number of Trees, Cartesian
Products and Some Infinite Graphs"
Douglas Rall (Furman U, USA), Bostjan
Bresar (U Maribor, Slovenia), Arthur
Finbow (Saint Mary's U, Canada) and
Sandi Klavzar (U Maribor, Slovenia)
13:10-14:30: Lunch:
14:30: Plenary Talk J (Room Petrohue)
Chair: François Margot
14:30 - 15:20 l Dominique
de Werra (EPFL, Switzerland)
"Coloring mixed graphs"
Room Petrohue:
15:30-16:30: Colorings of Graphs III - Chair: Florian
Huc
15:30-15:50: "Bounding the pseudoachromatic index of the complete
graph via projective planes"
Gabriela Araujo-Pardo (IM, UNAM, Mexico)
and Ricardo Strausz (IM, UNAM, Mexico)
15:50-16:10: "The Proportional Colouring Problem: Optimizing Buffers
in Radio Mesh Networks"
Florian Huc (I3S CNRS-UNSA, INRIA, France),
Cláudia Linhares-Sales (UFC, Brazil)
and Hervé Rivano (I3S CNRS-UNSA, INRIA, France)
16:10-16:30: "List Colouring Constants of Triangle Free Graphs"
Omid Amini (Projet Mascotte, I3S-CNRS/UNSA/INRIA,
France) and Bruce Reed (Projet Mascotte,
I3S-CNRS/UNSA/INRIA, France - McGill U, Canada)
Room Calbuco:
15:30-16:30: Computational Complexity II - Chair: Néstor
E. Aguilera
15:30-15:50: "The polynomial dichotomy for three nonempty part
sandwich problems"
Rafael Teixeira (UFRJ, Brazil), Celina
de Figueiredo (UFRJ, Brazil) and Simone
Dantas (UFF, Brazil)
15:50-16:10: "Algorithmic aspects of monophonic convexity"
Mitre Dourado (UFRRJ, Brazil), Fabio
Protti (UFRJ, Brazil) and Jayme Szwarcfiter
(UFRJ, Brazil)
16:10-16:30: "Combinatorial flexibility problems and their computational
complexity"
Néstor E. Aguilera (CONICET and UNL, Argentina),
Valeria A. Leoni (CONICET and UNR, Argentina)
and Graciela L. Nasini (CONICET and UNR, Argentina)
16:30-16:50: Coffee-Break
Room Petrohue:
16:50-17:50: Colorings of Graphs IV - Chair: Bernardo
Llano
16:50-17:10: "On a Conjecture of Víctor Neumann-Lara"
Bernardo Llano (UAM, Mexico) and Mika
Olsen (UAM, Mexico)
17:10-17:30: "Homomorphisms of 2-edge-colored graphs"
Amanda Montejano (U Polytecnica de Catalunya,
Spain), Pascal Ochem (LaBRI, U Bordeaux
1, France), Alexandre Pinlou (LaBRI,
U Bordeaux 1, France), André Raspaud (LaBRI,
U Bordeaux 1, France) and Éric Sopena (LaBRI,
U Bordeaux 1, France)
17:30-17:50: "Finding Folkman Numbers via MAX CUT Problem"
Andrzej Dudek (Emory U, USA) and Vojtech
Rodl (Emory U, USA)
Room Calbuco:
16:50-17:50: Approximation Algorithms - Chair: Yerim Chung
16:50-17:10: "Some Inverse Traveling Salesman Problems"
Yerim Chung (U Paris 1, France) and
Marc Demange (ESSEC Business School, France)
17:10-17:30: "4-cycles in mixing digraphs"
Omid Amini (INRIA CNRS I3S UNSA, France),
Simon Griffiths (Cambridge U, England)
and Florian Huc (INRIA CNRS I3S UNSA, France)
17:30-17:50: "Online Bounded Coloring of Permutation and Overlap
Graphs"
Marc Demange (ESSEC Business School, France),
Gabriele Di Stefano (U dell'Aquila, Italy)
and Benjamin Leroy-Beaulieu (EPFL, Switzerland)
20:30: Dinner (Club de Yates, Puerto Varas)
Thursday, 29th
08:30: Plenary Talk L (Petrohue Room)
Chair: Iván Rapaport
08:30 - 09:20 l Michel
Goemans (MIT, USA)
"Minimum bounded degree spanning trees"
09:20: Plenary Talk M (Petrohue Room)
Chair: Flavia Bonomo
09:20-10:10 l Annegret
Wagler (University of Magdeburg, Germany)
"Combinatorial aspects of the network reconstruction problem"
10:10-10:40: Coffee-Break
Room Petrohue:
10:40-11:20: Structural Characterizations of Graphs III
-
Chair: Claudia Linhares-Sales
10:40-11:00: "Partial characterizations of clique-perfect and coordinated
graphs: superclasses of triangle-free graphs"
Flavia Bonomo (CONICET and UBA, Argentina),
Guillermo Alfredo Durán (U Chile, Chile -
UBA, Argentina), Francisco Soulignac (UBA,
Argentina) and Gabriel Sueiro (UBA,
Argentina)
11:00-11:20: "Even-hole-free planar graphs have bounded treewidth"
Aline Alves da Silva (UFC, Brazil),
Ana Silva (UFC, Brazil) and Claudia
Linhares-Sales (UFC, Brazil)
Room Calbuco:
10:40-11:20: Combinatorial Optimization II - Chair:
Pablo Saez
10:40-11:00: "A Quadratic Algorithm for the 2-Cyclic Robotic Scheduling
Problem"
Pablo Saez (U Concepcion, Chile)
11:00-11:20: "The maximum number of halving lines and the rectilinear
crossing number of Kn for $n \leq 27$"
Silvia Fernández-Merchant (California State
U, USA), Bernardo M. Ábrego (California
State U, USA), Jesús Leaños (U Autónoma
de San Luis Potosí, México) and Gelasio Salazar (U
Autónoma de San Luis Potosí, México)
11:30:: Plenary Talk N (Room Petrohue)
Chair: Eduardo Moreno
11:30-12:20 l Stéphan
Thomassé (University Montpellier 2 - LIRMM,
France)
"Cyclic Orderings of Matroids"
12:20: Plenary Talk O (Room Petrohue)
Chair: Daniel Espinoza
12:20-13:10 l Roberto
Cominetti (University of Chile, Chile)
"Equilibrium and learning in traffic network games"
13:10-13:20: LAGOS'07 Closing Session (Room Petrohue)
13:20-14:30: Lunch
|