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).
翻译:我们提出了连接测试和相关问题的固定时间算法的实施。有些是实施稍有改进的先前已知算法的变种;对于其他问题,我们提出的新算法的运行时间大大高于以往已知算法(连接的距离和宽容测试器估计值、连接的两端-连接性、连接的三端-连接性、电子性)。