Campus Event Calendar
Event Entry
What and Who
Breaking through the O(m^2 n) Barrier for Minimum Cycle Bases
Tomasz Jurkiewicz
International Max Planck Research School for Computer Science - IMPRS
Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 5 November 2009
17:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
Cycles in graphs play an important role in many applications, e.g. analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. Cycle bases are a compact description of the set of all cycles of a graph and cycle bases consisting of short cycles or, in weighted graphs, of small weight cycles are preferable.
We present an algorithm for computing general minimum weight cycle bases in time O(E^omega) for general graphs; here V and E denote the number of nodes and edges, respectively, and omega is the exponent of the fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Õ(E^2 V). A key to our improved running time is the insight that the search for the minimum basis can be restricted to a set of candidate cycles of total length O(V E).
We present an algorithm for computing general minimum weight cycle bases in time O(E^omega) for general graphs; here V and E denote the number of nodes and edges, respectively, and omega is the exponent of the fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Õ(E^2 V). A key to our improved running time is the insight that the search for the minimum basis can be restricted to a set of candidate cycles of total length O(V E).
Contact
imprs
225
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 11/02/2009 17:04 -- Created document.