Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Convex cycle bases
 Ars mathematica contemporanea 7 (2014), No.1, pp.123140 ISSN: 18553966 ISSN: 18553974 

 English 
 Journal Article 
 Fraunhofer IZI () 
Abstract
Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomialtime algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs.