voltarData: 12/05/2021
Título: Maximum cut and Steiner tree restricted to interval graphs and related families.
Palestrante: Celina Figueiredo, COPPE/UFRJ.
Data: 12 de Maio de 2021, 15:30 h.
Sala: Google Meet.
The Combinatory Seminar celebrates once again the International Women's Day in Mathematics. To celebrate this date, we will have the honor of welcoming Professor Celina M. H. de Figueiredo. Researcher PQ 1A-CNPQ, Celina is the first woman at the Alberto Luiz Coimbra Institute for Graduate Studies and Engineering Research at the Federal University of Rio de Janeiro (COPPE), the largest engineering teaching and research center in Latin America, to receive the Giulio Massarani Award for Academic Merit (2006) and to be approved in a public competition, open to the area of Systems and Computer Engineering, as a full professor at COPPE (2011).
Abstract: We consider Column 16 -- Graph Restrictions and Their Effect -- of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns, and several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We focus on columns MaxCut and StTree, where there are recent resolved entries for interval graphs and related families.
Veja: Apresentação Vídeo Chat