On the public citation graph

A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities

https://doi.org/10.1145/3380546
0 signed · 45 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.1006/jagm.1998.0929openalex-snapshot
Fast Distributed Construction of Smallk-Dominating Sets and Applications
inferredcites →https://doi.org/10.1007/bf01303516openalex-snapshot
Low diameter graph decompositions
inferredcites →https://doi.org/10.1007/bf02242717openalex-snapshot
A highly asynchronous minimum spanning tree protocol
inferredcites →https://doi.org/10.1007/s00446-004-0107-2openalex-snapshot
A linear-time optimal-message distributed algorithm for minimum spanning trees
inferredcites →https://doi.org/10.1007/s00446-005-0127-6openalex-snapshot
Distributed MST for constant diameter graphs
inferredcites →https://doi.org/10.1007/s00446-007-0047-8openalex-snapshot
A fast distributed approximation algorithm for minimum spanning trees
inferredcites →https://doi.org/10.1016/s0019-9958(86)80023-7openalex-snapshot
Deterministic coin tossing with applications to optimal parallel list ranking
inferredcites →https://doi.org/10.1109/sfcs.1985.7openalex-snapshot
An almost linear time and O(nlogn+e) Messages distributed algorithm for minimum-weight spanning trees
inferredcites →https://doi.org/10.1109/sfcs.1993.366822openalex-snapshot
Fast algorithms for constructing t-spanners and paths with stretch t
inferredcites →https://doi.org/10.1109/sfcs.1993.366823openalex-snapshot
Near-linear cost sequential and distributed constructions of sparse neighborhood covers
inferredcites →https://doi.org/10.1109/sffcs.1999.814597openalex-snapshot
A near-tight lower bound on the time complexity of distributed MST construction
inferredcites →https://doi.org/10.1137/1.9780898719772openalex-snapshot
Distributed Computing: A Locality-Sensitive Approach
inferredcites →https://doi.org/10.1137/1.9781611974331.ch16openalex-snapshot
Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
inferredcites →https://doi.org/10.1137/11085178xopenalex-snapshot
Distributed Verification and Hardness of Distributed Approximation
inferredcites →https://doi.org/10.1137/s0097539704441848openalex-snapshot
Minimum-Weight Spanning Tree Construction in O (log log n ) Communication Rounds
inferredcites →https://doi.org/10.1137/s0097539794261118openalex-snapshot
A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
inferredcites →https://doi.org/10.1145/1007352.1007407openalex-snapshot
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
inferredcites →https://doi.org/10.1145/2611462.2611488openalex-snapshot
Can quantum communication speed up distributed computation?
inferredcites →https://doi.org/10.1145/2767386.2767405openalex-snapshot
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
inferredcites →https://doi.org/10.1145/2767386.2767434openalex-snapshot
Toward Optimal Bounds in the Congested Clique
inferredcites →https://doi.org/10.1145/2933057.2933103openalex-snapshot
MST in Log-Star Rounds of Congested Clique
inferredcites →https://doi.org/10.1145/2933057.2933112openalex-snapshot
Low-Congestion Shortcuts without Embedding
inferredcites →https://doi.org/10.1145/3007748.3007775openalex-snapshot
Time-communication trade-offs for minimum spanning tree construction
inferredcites →https://doi.org/10.1145/3087801.3087823openalex-snapshot
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities
inferredcites →https://doi.org/10.1145/3212734.3212737openalex-snapshot
Round- and Message-Optimal Distributed Graph Algorithms
inferredcites →https://doi.org/10.1145/323596.323612openalex-snapshot
Improvements in the time complexity of two message-optimal election algorithms
inferredcites →https://doi.org/10.1145/357195.357200openalex-snapshot
A Distributed Algorithm for Minimum-Weight Spanning Trees
inferredcites →https://doi.org/10.1145/77600.77618openalex-snapshot
A trade-off between information and communication in broadcast protocols
inferredcites →https://doi.org/10.5555/982792.982844openalex-snapshot
A faster distributed protocol for constructing a minimum spanning tree

What points at this work

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

inferred← citeshttps://doi.org/10.1007/978-3-031-60603-8_17openalex-snapshot
Towards Singular Optimality in the Presence of Local Initial Knowledge
inferred← citeshttps://doi.org/10.1007/s00446-020-00373-4openalex-snapshot
Fooling views: a new lower bound technique for distributed computations under congestion
inferred← citeshttps://doi.org/10.1007/s00446-025-00483-xopenalex-snapshot
Tight bounds on the message complexity of distributed tree verification
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.11.006openalex-snapshot
Latency, capacity, and distributed minimum spanning trees
inferred← citeshttps://doi.org/10.1137/1.9781611975482.51openalex-snapshot
Distributed Triangle Detection via Expander Decomposition
inferred← citeshttps://doi.org/10.1145/3055399.3055449openalex-snapshot
A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
inferred← citeshttps://doi.org/10.1145/3212734.3212776openalex-snapshot
Minor Excluded Network Families Admit Fast Distributed Algorithms
inferred← citeshttps://doi.org/10.1145/3313276.3316326openalex-snapshot
Distributed exact weighted all-pairs shortest paths in near-linear time
inferred← citeshttps://doi.org/10.1145/3382734.3405701openalex-snapshot
Distributed Construction of Light Networks
inferred← citeshttps://doi.org/10.1145/3406325.3451081openalex-snapshot
Universally-optimal distributed algorithms for known topologies
inferred← citeshttps://doi.org/10.1145/3465084.3467909openalex-snapshot
Can We Break Symmetry with o(m) Communication?
inferred← citeshttps://doi.org/10.1145/3796701.3815917openalex-snapshot
Efficient Counting and Simulation in Content-Oblivious Rings
inferred← citeshttps://doi.org/10.1145/3816782.3819194openalex-snapshot
Time-, Message- and Memory-Efficient Distributed Minimum Spanning Tree and Partwise Aggregation
inferred← citeshttps://doi.org/10.4230/lipics.disc.2020.11openalex-snapshot
Communication Efficient Self-Stabilizing Leader Election
inferred← citeshttps://doi.org/10.48550/arxiv.1708.03903openalex-snapshot
Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds
inferred← citeshttps://doi.org/10.48550/arxiv.1902.08979openalex-snapshot
Latency, Capacity, and Distributed MST
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.