非表示:
キーワード:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM
要旨:
We present a certifying algorithm that tests graphs for 3-edge-connectivity;
the algorithm works in linear time. If the input graph is not 3-edge-connected,
the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a
construction sequence that constructs the input graph from the graph with two
vertices and three parallel edges using only operations that (obviously)
preserve 3-edge-connectivity. Additionally, we show how compute and certify the
3-edge-connected components and a cactus representation of the 2-cuts in linear
time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected
components of a 2-connected graph.
