Program

Monday, May 11th
19:00 Welcome cocktail


Tuesday, May 12th
08:30 Opening ceremony
08:45 Plenary Session (João-de-Castro Room) - Chair: Frédéric Havet
Bruce Reed: Connectivity Preserving Iterative Compression
09:45 Coffee Break
10:00 João-de-Castro Room: Graph Algorithms - Chair: Flavia Bonomo
Using SPQR-trees to speed up algorithms based on 2-cutset decompositions - Celina Figueiredo, Zhentao Li, Helio Macedo Filho, Raphael Machado and Nicolas Trotignon
Some links between identifying codes and separating, dominating and total dominating sets in graphs - Graciela Nasini and Pablo Torres
On f-Reversible Processes on Graphs - Mitre Costa Dourado, Carlos Vinicius G.C. Lima and Jayme Luiz Szwarcfiter
10:00 Simão Room: Polyhedral Combinatorics - Chair: Yoshiko Wakabayashi
Flow-based formulation for the maximum leaf spanning tree problem - Márcio F. Reis, Orlando Lee and Fábio L. Usberti
An algebraic-perturbation variant of Barvinok's algorithm - Jon Lee and Daphne Skipper
The caterpillar-packing polytope - Javier Marenco
10:00 Régis-Jucá Room: Extremal Graph Theory - Chair: Guilherme Mota
Edge-colorings avoiding fixed rainbow stars - Carlos Hoppen, Hanno Lefmann, Knut Odermann and Juliana Sanches
A counting lemma for sparse pseudorandom hypergraphs - Yoshiharu Kohayakawa, Guilherme O. Mota, Mathias Schacht and Anusch Taraz
On the average path length of a cycle plus random edges - Dimbinaina Ralaivaosaona and Samah Taha
11:15 Break
11:30 Plenary Session (João-de-Castro Room) - Chair: Yoshiko Wakabayashi
Ola Svensson: Algorithms for the Asymmetric Traveling Salesman Problem
12:30 Lunch Break
16:00 João-de-Castro Room: Graph Algorithms - Chair: Mario Valencia-Pabon
On Graphs with Induced Matching Number Almost Equal to Matching Number - Uéverton Souza, Dieter Rautenbach, Lucia Draque Penso, Felix Joos and Marcio Duarte
Graph Saturation Games - Jonathan Lee and Ago-Erik Riet
A new reversible circuit synthesis algorithm based on cycle representations of permutations - Andre Ribeiro, Luis Kowada, Franklin Marquezino and Celina Figueiredo
16:00 Simão Room: Polyhedral Combinatorics - Chair: Manoel Campelo
The k-hop connected dominating set problem: hardness and polyhedra - Rafael Santos Coelho, Phablo Fernando Soares Moura and Yoshiko Wakabayashi
A polyhedral approach to locating-dominating sets in graphs - Gabriela Argiroffo, Silvia Bianchi and Annegret Wagler
A Strengthened General Cut-Generating Procedure for the Stable Set Polytope - Ricardo Corrêa, Javier Marenco, Diego Delle Donne and Ivo Koch
16:00 Régis-Jucá Room: Structural Graph Theory - Chair: Cláudia Linhares Sales
On containment graphs of paths in a tree - Liliana Alcón, Noemi Gudiño and Marisa Gutierrez
Decompositions of highly connected graphs into paths of length five - Fábio Botler, Guilherme O. Mota, Márcio T.I. Oshiro and Yoshiko Wakabayashi
Optimal Edge Fault-Tolerant Bijective Embedding of a Complete Graph over a Cycle - Eduardo Alberto Canale Bentancourt and Claudio Risso
17:15 Coffee Break
17:30 Plenary Session (João-de-Castro Room) - Chair: Ana Shirley Silva
Frédéric Havet: Induced subdigraphs of digraphs with large chromatic number
18:30 Break
18:45 João-de-Castro Room: Graph Algorithms - Chair: Nicolas Nisse
Minimum Size Tree-decompositions - Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan
Budgeted sensor placement for source localization on trees - Elisa Celis, Filip Pavetic, Brunella Spinelli and Patrick Thiran
Efficient and Perfect domination on circular-arc graphs - Min Chih Lin, Michel J. Mizrahi and Jayme L. Szwarcfiter
18:45 Simão Room: Structural Graph Theory - Chair: Fabricio Benevides
Geodeticity of the contour of chordal bipartite graphs - D. Artigas and R. Sritharan
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid - Liliana Alcon, Flavia Bonomo, Guillermo Durán, Marisa Gutierrez, Maria Pia Mazzoleni, Bernard Ries and Mario Valencia-Pabon
Tight lower bounds on the number of bicliques in false-twin-free graphs - Marina Groshaus and Leandro Montero
18:45 Régis-Jucá Room: Graph Coloring - Chair: Leonardo Rocha
The 1,2-Conjecture for powers of cycles - Atílio Luiz, Christiane Campos, Simone Dantas and Diana Sasaki
On oriented relative clique number - Sandip Das, Swathyprabhu Mj and Sagnik Sen
Weighted antimagic labeling: an algorithmic approach - José Zamora and Martín Matamala


Wednesday, May 13th
8:30 João-de-Castro Room: Fixed-Parameter Tractability - Chair: Fábio Protti
Fly-automata for checking monadic second-order properties of graphs of bounded tree-width - Bruno Courcelle
Roman domination in subgraphs of grids - Samuel Nascimento and Rudini Sampaio
The Flood-It game parameterized by the vertex cover number - Frances Rosamond, Michael Fellows, Uéverton Souza, Fabio Protti and Maise Dantas Da Silva
8:30 Simão Room: Polyhedral Combinatorics - Chair: Javier Marenco
Partitions of Rectilinear Polygons with Minimum Stabbing Number - Breno Piva and Cid C. De Souza
An algorithm for solving parametric integer programming - Norie Fu and Takafumi Shibuta
Minor related row family inequalities for the set covering polyhedron of circulant matrices - Luis M. Torres
8:30 Régis-Jucá Room: Structural Graph Theory - Chair: Carlos Hoppen
Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles - Oliver Schaudt and Maya Stein
On second iterated clique graphs that are also third iterated clique graphs - Pablo De Caria and Miguel Ángel Pizaña
On the hereditary (p,q)-Helly property of hypergraphs, cliques, and bicliques - Mitre Costa Dourado, Luciano Norberto Grippo and Martín Darío Safe
9:45 Coffee Break
10:00 Plenary Session (João-de-Castro Room) - Chair: Cláudia Linhares Sales
Frédéric Maffray: Coloring square-free Berge graphs
11:00 Break
11:15 João-de-Castro Room: Graph Algorithms - Chair: Flavia Bonomo
Inapproximability of the lid-chromatic number - Nicolas Martins and Rudini Sampaio
Pebbling in 2-paths - Glenn Hurlbert, Liliana Alcon and Marisa Gutierrez
Chronological Rectangle Digraphs - Jing Huang and Josh Manzer
11:15 Simão Room: Structural Graph Theory - Chair: Victor Campos
Kneser Transversals - Luis Montejano, Jonathan Chappelon, Leonardo Martínez, Luis Pedro Montejano and Jorge Ramirez-Alfonsin
Compatibility, Incompatibility, Tree-Width, and Forbidden Phylogenetic Minors - Sudheer Vakati and David Fernández-Baca
Graphs with few critical ideals - Carlos Alejandro Alfaro and Carlos Enrique Valencia
11:15 Régis-Jucá Room: Computational Geometry - Chair: Cristina Fernandes
Trajectory clustering of points in R - Cristina Fernandes and Marcio T. I. Oshiro
Diagonalization of generalized lollipop graphs - Renata Del-Vecchio, David Jacobs, Vilmar Trevisan and Cybele Vinagre
An algorithm for realizing Euclidean distance matrices - Jorge Alencar, Tibérius Bonates, Carlile Lavor and Leo Liberti
12:30 Lunch Break
13:30 Excursion


Thursday, May 14th
8:30 João-de-Castro Room: Structural Graph Theory - Chair: Júlio Araújo
Quasiperfect Domination in Trees - Ignacio M. Pelayo, José Cáceres, Carmen Hernando, Mercè Mora and M.L. Puertas
On unit interval graphs with integer endpoints - Florencia Fernández Slezak, Guillermo Durán, Luciano Grippo, Fabiano Oliveira and Jayme Szwarcfiter
Isolation in graphs - Adriana Hansberg and Yair Caro
8:30 Simão Room: Polyhedral Combinatorics - Chair: Diego Delle Donne
On the Path Avoiding Forbidden Pairs Polytope - Marco Blanco, Ralf Borndörfer, Michael Brückner, Nam Dũng Hoàng and Thomas Schlechte
The Set Packing Polytope: A Computational Study of Conflict Graphs and Aggressive Cut Separation - Samuel Souza Brito, Haroldo Gambini Santos and Marcus Poggi
The Ring Tree Facility Location Problem - Fabio Abe, Edna Hoshino and Alessandro Hill
8:30 Régis-Jucá Room: Extremal Graph Theory - Chair: Maya Stein
High degrees in Recursive Trees - Laura Eslava and Louigi Addario-Berry
Ramsey-type numbers involving graphs and hypergraphs with large girth - Hiep Han, Troy Retter, Vojtech Rodl and Mathias Schacht
Excluding clocks - Pierre Aboulker, Zhentao Li and Stéphan Thomassé
9:45 Coffee Break
10:00 Plenary Session (João-de-Castro Room) - Chair: Manoel Campelo
Gerard Cornuejols: Cut-Generating Functions for Integer Linear Programs
11:00 Break
11:15 João-de-Castro Room: Approximation Algorithms - Chair: Cristina Fernandes
A hierarchical network formation model - Omid Atabati and Babak Farzad
Approximating Minimum k-Section in Trees with Linear Diameter - Cristina Fernandes, Tina Janne Schmidt and Anusch Taraz
Toward an 11/9 bound for the minimum cost 2-edge connected subgraph problem - Sylvia Boyd and Philippe Legault
11:15 Simão Room: Extremal Graph Theory - Chair: Victor Campos
A Proof for a Conjecture of Gorgol - Victor Campos and Raul Lopes
Fractional Turan's theorem and bounds for the chromatic number - Leonardo Ignacio Martínez Sandoval and Luis Montejano
11:15 Régis-Jucá Room: Online Algorithms - Chair: Yoshiko Wakabayashi
The Online Prize-Collecting Facility Location Problem - Mário César San Felice, Sin-Shuen Cheung, Orlando Lee and David P. Williamson
On the Online Min-Wait Relocation Problem - Pascal Halffmann, Sven Krumke, Alain Quilliot, Annegret Wagler and Jan-Thierry Wegener
12:30 Lunch Break
16:00 Plenary Session (João-de-Castro Room) - Chair: Jayme Luiz Szwarcfiter
Sulamita Klein: Complexity of Graph Sandwich Problems Related to Partition Problems
17:00 Break
17:15 João-de-Castro Room: Complexity - Chair: Vinícius dos Santos
Computing an Evolutionary Ordering is Hard - Laurent Bulteau, Gustavo Sacomoto and Blerina Sinaimeri
NP-completeness of the {k}-packing function problem in graphs - Valeria Leoni, María Patricia Dobson and Erica Hinrichsen
Complexity of determining the maximum infection time in the geodetic convexity - Fabricio S. Benevides, Victor Campos, Mitre Dourado and Ana Silva
17:15 Simão Room: Topological Graph Theory - Chair: Guilherme Mota
A min-max relation in flowgraphs - Carlos Ferreira and Alvaro Franco
Many disjoint edges in topological graphs - Andres J. Ruiz-Vargas
On Rotational Symmetries of Drawings of Coherent Periodic Graphs - Tetsuya Araki and Norie Fu
17:15 Régis-Jucá Room: Graph Coloring - Chair: Ana Karolinna Maia de Oliveira
b-continuity and the lexicographic product of graphs - Cláudia Linhares Sales, Rafael Vargas and Leonardo Sampaio
Steinberg-like theorems for backbone colouring - Julio Araujo, Frédéric Havet and Mathieu Schmitt
k-tuple chromatic number of the cartesian product of graphs - Flavia Bonomo, Ivo Koch, Pablo Torres and Mario Valencia-Pabon
19:30 LAGOS 2015 Dinner


Friday, May 15th
8:15 Plenary Session (João-de-Castro Room) - Chair: Flavia Bonomo
Miguel Pizaña: Discrete Homotopy on Graphs and Clique Graphs
9:15 Break
9:20 João-de-Castro Room: Graph classes - Chair: Nicolas Nisse
Structural characterization and decomposition for cographs-(2,1) and (1,2): a natural generalization of threshold graphs - Fernanda Couto, Luerbio Faria, Sylvain Gravier, Sulamita Klein and Vinícius F. Dos Santos
On path decompositions of 2k-regular graphs - Fábio Botler and Andrea Jiménez
On the chromatic index of cographs and join graphs - Alex Cunha Lima, Georgia Garcia, Leandro Zatesko and Sheila Almeida
9:20 Simão Room: Graph Theory - Chair: Ana Shirley Silva
Hypohamiltonian Snarks Have a 5-Flow - Breno L. de Freitas, Cândida Nunes Da Silva and Cláudio L. Lucchesi
Three-colourability of planar graphs with no 5- or triangular {3,6}-cycles - Babak Farzad and Asiyeh Sanaei
A Faster Test for 4-Flow-Criticality in Snarks - André B. Carneiro, Cândida Nunes Da Silva and Brendan McKay
9:20 Régis-Jucá Room: Poster Session
10:50 Coffee Break