Linear expected-time algorithms for connectivity problems
From MaRDI portal
Publication:3914449
DOI10.1016/0196-6774(80)90017-6zbMath0463.68060OpenAlexW2080548021MaRDI QIDQ3914449
Richard M. Karp, Robert Endre Tarjan
Publication date: 1980
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(80)90017-6
analysis of algorithmsgraph connectivityminimum spanning forestrandom graph modelfast average-time algorithms
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Algorithms in computer science (68W99)
Related Items
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Sufficient set of integrability conditions of an orthonomic system, Average case analysis of fully dynamic connectivity for directed graphs, Expected parallel time and sequential space complexity of graph and digraph problems, Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time, Improved Side-Channel Collision Attacks on AES, Average case analysis of fully dynamic reachability for directed graphs, On some conditioning results in the probabilistic analysis of algorithms
Uses Software
