Colloquium Details
An Algorithm for Cyclic Edge Connectivity of Cubic Graphs
| Author: | Daniel Kral Charles University, Prague; School of Mathematics, Georgia Institute of Technology, Atlanta |
|---|---|
| Date: | May 11, 2006 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
The ordinary graph connectivity parameters do not work well for graphs with low minimum/average vertex degree. Such classes of graphs include planar graphs and cubic graphs. One of the graph parameters that deals with this issue is cyclic connectivity that was introduced by Tait already in 1880. The cyclic edge connectivity of a graph is the size of the smallest edge cut such that at least two of the parts of the graph are not acyclic. This parameter naturally appears in several scenarios both in theory, let us mention the proof of the Four Color Theorem or the notion of snarks (cubic graphs that are not 3-edge-colorable), and in practice whenever sparse graphs appear.
We present two algorithms for computing cyclic edge connectivity of cubic graphs, one running in time O(n^3 log n) and the other in time O(n^2 log^2 n). Both our algorithms are simple to implement and their running time bounds do not involve any hidden large constants. So, either of them can be said to be practical. Our technique generalizes to graphs with bounded maximum degree keeping the same time bounds as well as it can be adopted to yield a polynomial-time algorithm for computing the cyclic edge-connectivity of general graphs.