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   -

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).

View abstract PDF