10 citations · 19 across the 18 of their papers we have counts for
Showing 2012 · cs.DSShow all
3 papers · 2 filters
cs.DS2012★ 10 cited
Certifying 3-Edge-Connectivity
Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt
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…
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.DS2012
A Planarity Test via Construction Sequences
Jens M. Schmidt
Optimal linear-time algorithms for testing the planarity of a graph are well-known for over 35 years. However, these algorithms are quite involved and recent publications still try…