Convex Cycle Bases

Marc Hellmuth, Josef Leydold, Peter F. Stadler

Publication: Working/Discussion PaperWU Working Paper

24 Downloads (Pure)

Abstract

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. (authors' abstract)
Original languageEnglish
Place of PublicationVienna
PublisherWU Vienna University of Economics and Business
DOIs
Publication statusPublished - 2013

Publication series

SeriesResearch Report Series / Department of Statistics and Mathematics
Number124

WU Working Paper Series

  • Research Report Series / Department of Statistics and Mathematics

Cite this