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

    [view as a table] [pdf version]