2 papers
cs.DS2012
A Simple Test on 2-Vertex- and 2-Edge-Connectivity
Jens M. Schmidt
Testing a graph on 2-vertex- and 2-edge-connectivity are two fundamental algorithmic graph problems. For both problems, different linear-time algorithms with simple implementations…
cs.DS2010
Contractions, Removals and How to Certify 3-Connectivity in Linear Time
Jens M. Schmidt
It is well-known as an existence result that every 3-connected graph G=(V,E) on more than 4 vertices admits a sequence of contractions and a sequence of removal operations to K_4 s…