Linear expected-time algorithms for connectivity problems

DOI10.1016/0196-6774(80)90017-6MaRDI QIDQ3914449zbMATH OpenOpenAlexFDO

Authors Richard Karp, Robert E. 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

zbMATH Keywords

analysis of algorithmsfast average-time algorithmsgraph connectivityminimum spanning forestrandom graph model

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Cited in

(9)

• On some conditioning results in the probabilistic analysis of algorithms
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• Expected parallel time and sequential space complexity of graph and digraph problems
• Sufficient set of integrability conditions of an orthonomic system
• Average case analysis of fully dynamic reachability for directed graphs
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• 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 connectivity for directed graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Linear expected-time algorithms for connectivity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3914449)