On the public citation graph

Expected parallel time and sequential space complexity of graph and digraph problems

https://doi.org/10.1007/bf01758779
0 signed · 48 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-3-642-75357-2_5openalex-snapshot
Uniform Circuit Complexity
inferredcites →https://doi.org/10.1007/bfb0012790openalex-snapshot
On the power of probabilistic choice in synchronous parallel computations
inferredcites →https://doi.org/10.1007/bfb0105127openalex-snapshot
Finding the maximum, merging and sorting in a parallel computation model
inferredcites →https://doi.org/10.1016/0012-365x(85)90079-2openalex-snapshot
k-connectivity in random undirected graphs
inferredcites →https://doi.org/10.1016/0016-0032(58)90688-4openalex-snapshot
An introduction to probability theory and its applications
inferredcites →https://doi.org/10.1016/0020-0190(82)90093-xopenalex-snapshot
Parallel computation and conflicts in memory access
inferredcites →https://doi.org/10.1016/0022-0000(79)90045-xopenalex-snapshot
Fast probabilistic algorithms for hamiltonian circuits and matchings
inferredcites →https://doi.org/10.1016/0022-0000(85)90008-xopenalex-snapshot
Routing, merging, and sorting on parallel models of computation
inferredcites →https://doi.org/10.1016/0196-6774(80)90017-6openalex-snapshot
Linear expected-time algorithms for connectivity problems
inferredcites →https://doi.org/10.1016/0196-6774(81)90010-9openalex-snapshot
Finding the maximum, merging, and sorting in a parallel computation model
inferredcites →https://doi.org/10.1016/0196-6774(82)90008-6openalex-snapshot
An O(logn) parallel connectivity algorithm
inferredcites →https://doi.org/10.1016/0196-6774(82)90013-xopenalex-snapshot
An O(n2log n) parallel max-flow algorithm
inferredcites →https://doi.org/10.1016/0304-3975(82)90058-5openalex-snapshot
Symmetric space-bounded computation
inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot
Relationships between nondeterministic and deterministic tape complexities
inferredcites →https://doi.org/10.1090/cbms/062/06openalex-snapshot
The Evolution of Random Graphs
inferredcites →https://doi.org/10.1109/sfcs.1979.31openalex-snapshot
On uniform circuit complexity
inferredcites →https://doi.org/10.1109/sfcs.1979.34openalex-snapshot
Random walks, universal traversal sequences, and the complexity of maze problems
inferredcites →https://doi.org/10.1109/sfcs.1979.8openalex-snapshot
Canonical labelling of graphs in linear average time
inferredcites →https://doi.org/10.1109/sfcs.1981.21openalex-snapshot
Maximum matching in sparse random graphs
inferredcites →https://doi.org/10.1109/sfcs.1986.9openalex-snapshot
An optimal randomized parallel algorithm for finding connected components in a graph
inferredcites →https://doi.org/10.1109/sfcs.1987.46openalex-snapshot
Parallel graph algorithms that are efficient on average
inferredcites →https://doi.org/10.1137/0207011openalex-snapshot
An Algorithm for Transitive Closure with Linear Expected Time
inferredcites →https://doi.org/10.1137/0209047openalex-snapshot
Random Graph Isomorphism
inferredcites →https://doi.org/10.1137/0210049openalex-snapshot
Parallel Matrix and Graph Algorithms
inferredcites →https://doi.org/10.1137/0210051openalex-snapshot
Fast, Efficient Parallel Algorithms for Some Graph Problems
inferredcites →https://doi.org/10.1137/0220066openalex-snapshot
An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
inferredcites →https://doi.org/10.1145/12130.12151openalex-snapshot
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms
inferredcites →https://doi.org/10.1145/358628.358650openalex-snapshot
Efficient parallel algorithms for some graph problems
inferredcites →https://doi.org/10.1145/359138.359141openalex-snapshot
Computing connected components on parallel computers
inferredcites →https://doi.org/10.1145/62.322436openalex-snapshot
Symmetric Complementation
inferredcites →https://doi.org/10.1145/800133.804336openalex-snapshot
A unified approach to models of synchronous parallel machines
inferredcites →https://doi.org/10.1145/800133.804339openalex-snapshot
Parallelism in random access machines
inferredcites →https://doi.org/10.1145/800141.804686openalex-snapshot
Linear expected-time algorithms for connectivity problems (Extended Abstract)
inferredcites →https://doi.org/10.1145/800141.804688openalex-snapshot
Random matroids
inferredcites →https://doi.org/10.1145/800220.806702openalex-snapshot
N-processors graphs distributively achieve perfect matchings in O(log2N) beats
inferredcites →https://doi.org/10.1214/aoms/1177729330openalex-snapshot
A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
inferredcites →https://doi.org/10.2307/1401805openalex-snapshot
An Introduction to Probability Theory and Its Applications, Vol. 2

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11561071_49openalex-snapshot
An Experimental Study of Algorithms for Fully Dynamic Transitive Closure
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_71openalex-snapshot
Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
inferred← citeshttps://doi.org/10.1007/978-3-319-24024-4_1openalex-snapshot
A Glimpse at Paul G. Spirakis
inferred← citeshttps://doi.org/10.1007/s12539-011-0062-0openalex-snapshot
A comparative analysis of parallel computing approaches for genome assembly
inferred← citeshttps://doi.org/10.1016/s0196-6774(03)00076-2openalex-snapshot
Δ-stepping: a parallelizable shortest path algorithm
inferred← citeshttps://doi.org/10.1109/ipdps.2002.1015582openalex-snapshot
Buckets strike back: improved parallel shortest-paths
inferred← citeshttps://doi.org/10.1145/1109557.1109623openalex-snapshot
A computational study of external-memory BFS algorithms
inferred← citeshttps://doi.org/10.1145/1227161.1370597openalex-snapshot
An experimental study of algorithms for fully dynamic transitive closure
inferred← citeshttps://doi.org/10.22028/d291-25720openalex-snapshot
Design and analysis of sequential and parallel single-source shortest-paths algorithms
inferred← citeshttps://doi.org/10.22028/d291-25941openalex-snapshot
Traversing large graphs in realistic settings
inferred← citeshttps://doi.org/10.5555/1109557.1109623openalex-snapshot
A computational study of external-memory BFS algorithms
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.