Quotation Hellmuth, Marc, Leydold, Josef, Stadler, Peter F.. 2014. Convex Cycle Bases. Ars Mathematica Contemporanea 7 (1): 123-140.




Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time 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.


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal Ars Mathematica Contemporanea
Citation Index SCI
Language English
Title Convex Cycle Bases
Volume 7
Number 1
Year 2014
Page from 123
Page to 140
URL http://amc-journal.eu/index.php/amc/article/view/226


Leydold, Josef (Details)
Hellmuth, Marc
Stadler, Peter F.
Institute for Statistics and Mathematics IN (Details)
Research Institute for Computational Methods FI (Details)
Google Scholar: Search