2020/10/09 by Philipp Klaus Krause, Krause, Philipp Klaus
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #G.2.2 #G.3 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2010.04527
openalex publication_date 2020/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present implementations of constant-time algorithms for connectivity tests and related problems. Some are implementations of slightly improved variants of previously known algorithms; for other problems we present new algorithms that have substantially better runtime than previously known algorithms (estimates of the distance to and tolerant testers for connectivity, 2-edge-connectivity, 3-edge-connectivity, eulerianity).