FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 12, 18:00 ~ 18:30 - Room B11
Algorithms and complexity of graph convexity problems
Vinícius dos Santos
Centro Federal de Educação Tecnológica de Minas Gerais, Brazil - viniciussantos@decom.cefetmg.br
Several results concerning convex sets, originally studied on the Euclidean space, have been generalized for abstract convexities. In particular, the results of Carathéodory, Helly and Radon are among the most famous and well-studied. In the last forty years, graph convexities have been studied and graph analogues of classical results have been obtained. More recently, computational aspects have been the focus of many papers of this area.
In this talk we highlight some algorithmic and complexity results of convexity parameters on graphs, discuss some relations with conversion problems and present some open problems.
Joint work with Jayme L. Szwarcfiter (Universidade Federal do Rio de Janeiro, Brazil).