Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14297
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
URI: https://depositonce.tu-berlin.de/handle/11303/15524
http://dx.doi.org/10.14279/depositonce-14297
License: http://rightsstatements.org/vocab/InC/1.0/
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:
Report-031-2004.pdf
Format: Adobe PDF | Size: 522.67 kB
DownloadShow Preview
Thumbnail
Report-031-2004.ps.gz
Format: Unknown | Size: 1.34 MB
Download

Item Export Bar

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