Maximum cut and Steiner tree restricted to interval graphs and related families

Speaker: Celina de Figueiredo, COPPE UFRJ.

Date: 12 mai 2021, 14h.

Place: Google Meet: meet.google.com/nhe-vccv-qrf

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.