Convex Cycle Bases

Hellmuth, Marc and Leydold, Josef and Stadler, Peter F. (2014) Convex Cycle Bases. Ars Mathematica Contemporanea, 7 (1). pp. 123-140. ISSN 1855-3974

[img]
Preview
PDF
226-2089-1-PB.pdf
Available under License Creative Commons Attribution 3.0 Austria (CC BY 3.0 AT).

Download (368kB)

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.

Item Type: Article
Keywords: cycle basis, convex subgraph, isometric subgraph, Cartesian product, partial cubes
Classification Codes: Math. Subj. Class.: 05C15, 05C10
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Forschungsinstitute > Rechenintensive Methoden
Version of the Document: Published
Depositing User: Gertraud Novotny
Date Deposited: 20 Aug 2018 15:41
Last Modified: 19 Jul 2020 11:53
Related URLs:
FIDES Link: https://bach.wu.ac.at/d/research/results/64700/
URI: https://epub.wu.ac.at/id/eprint/6468

Actions

View Item View Item

Downloads

Downloads per month over past year

View more statistics