de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44586

Hariharan,  Ramesh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Hariharan, R., Telikepalli, K., & Mehlhorn, K. (2006). A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I (pp. 250-261). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-21DE-7
Zusammenfassung
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A {–1,0,1} edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get -1. The vector space over generated by these vectors is the cycle space of G. A minimum cycle basis is a set of cycles of minimum weight that span the cycle space of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in time (where ω< 2.376 is the exponent of matrix multiplication). Here we present an O(m3n + m2n2logn) algorithm. We also slightly improve the running time of the current fastest randomized algorithm from O(m2nlogn) to O(m2 n + mn2 logn).