Campus Event Calendar
Event Entry
What and Who
A (slow but) simple certifying test on the 3-connectedness of graphs
Jens Schmidt
Other:
AG1 Mittagsseminar (own work)
Freie Universität Berlin · Institute of Computer Science
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 11 August 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Hopcroft and Tarjan found over 30 years ago a linear-time test that is
able to test graphs on being 3-connected. This
algorithm is complex and difficult to implement correctly, and even
though some new tests were developed over the time there has not been
much progress in simplifying it, nor on extending it to give an
easy-to-ceck certificate along with its answer to justify it. We propose a new, simple test on the 3-connectedness of graphs that is based on a inductive construction and - in addition - constructs a certificate for the graphs that are 3-connected. The running time is O(n^2), the certificate has linear size and can be verified in linear time as well.
able to test graphs on being 3-connected. This
algorithm is complex and difficult to implement correctly, and even
though some new tests were developed over the time there has not been
much progress in simplifying it, nor on extending it to give an
easy-to-ceck certificate along with its answer to justify it. We propose a new, simple test on the 3-connectedness of graphs that is based on a inductive construction and - in addition - constructs a certificate for the graphs that are 3-connected. The running time is O(n^2), the certificate has linear size and can be verified in linear time as well.
Contact
Amr Elmasry
--email hidden
passcode not visible
logged in users only
Amr Elmasry, 07/31/2009 16:04 -- Created document.