Please use this identifier to cite or link to this item:
For citation please use:
Main Title: A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph
Author(s): Liebchen, Christian
Rizzi, Romeo
Type: Research Paper
Abstract: We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton and hereby obtain a very simple exact algorithm of complexity O(m4 n), being as fast as the first algorithm proposed for this problem. Moreover, the speed-up of Golynski and Horton applies to this problem, providing an exact algorithm of complexity O(mω n), in particular O(m3.376 n). Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.
Subject(s): minimum cycle bases
directed graphs
greedy algorithm
Issue Date: 2004
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 05C38 Paths and cycles
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2004, 31
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 522.67 kB
DownloadShow Preview
Format: Unknown | Size: 1.34 MB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.