University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
19.03.2012 Lecturer: dr. Oliver Schaudt (Universität zu Köln, Germany).
Title: The Price of Connectivity for Vertex Cover
Abstract: We study a graph parameter called the Price of Connectivity for Vertex Cover (PoC). It was recently introduced by Cardinal et al. and is defined as the ratio of the minimum size of a connected vertex cover and the minimum size of a vertex cover.We prove some structural results for the PoC. These results concern PoC-critical, PoC-perfect and PoC-near-perfect graphs.
Joint work with E. Camby, J. Cardinal and S. Fiorini.
Slides from the talk are available here: DOWNLOAD!
