On the public citation graph

A faster distributed protocol for constructing a minimum spanning tree

https://doi.org/10.1016/j.jcss.2006.07.002

0 signed · 76 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.1006/jpdc.1996.0159openalex-snapshot

Fast Distributed Network Decompositions and Covers

inferredcites →https://doi.org/10.1016/0890-5401(90)90014-9openalex-snapshot

Knowledge and common knowledge in a Byzantine environment: Crash failures

inferredcites →https://doi.org/10.1109/fscs.1990.89572openalex-snapshot

Network synchronization with polylogarithmic overhead

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.1989.63504openalex-snapshot

Network decomposition and locality in distributed computation

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/0221015openalex-snapshot

Locality in Distributed Graph Algorithms

inferredcites →https://doi.org/10.1137/0405013openalex-snapshot

Routing with Polynomial Communication-Space Trade-Off

inferredcites →https://doi.org/10.1137/1.9780898719772openalex-snapshot

Distributed Computing: A Locality-Sensitive Approach

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/1103963.1103968openalex-snapshot

Computing almost shortest paths

inferredcites →https://doi.org/10.1145/28395.28421openalex-snapshot

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

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/375551.375567openalex-snapshot

Optimal aggregation algorithms for middleware

inferredcites →https://doi.org/10.1145/383962.383983openalex-snapshot

Computing almost shortest paths

inferredcites →https://doi.org/10.1145/4221.4227openalex-snapshot

Complexity of network synchronization

inferredcites →https://doi.org/10.1145/73007.73054openalex-snapshot

Randomized distributed shortest paths algorithms

inferredcites →https://doi.org/10.5555/127787.127848openalex-snapshot

Decomposing graphs into regions of small diameter

What points at this work

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

inferred← citeshttps://doi.org/10.1002/9781119825968.ch7openalex-snapshot

Leader Election

inferred← citeshttps://doi.org/10.1007/11864219_25openalex-snapshot

A Fast Distributed Approximation Algorithm for Minimum Spanning Trees

inferred← citeshttps://doi.org/10.1007/978-3-319-46376-6_5openalex-snapshot

On the Microscopic View of Time and Messages

inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_13openalex-snapshot

Fast Distributed Computation of Cuts Via Random Circulations

inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_25openalex-snapshot

How to Use Spanning Trees to Navigate in Graphs

inferred← citeshttps://doi.org/10.1007/s00224-010-9280-9openalex-snapshot

Local MST Computation with Short Advice

inferred← citeshttps://doi.org/10.1007/s00446-007-0047-8openalex-snapshot

A fast distributed approximation algorithm for minimum spanning trees

inferred← citeshttps://doi.org/10.1007/s00446-012-0157-9openalex-snapshot

Efficient distributed approximation algorithms via probabilistic tree embeddings

inferred← citeshttps://doi.org/10.1007/s00446-017-0304-4openalex-snapshot

On efficient distributed construction of near optimal routing schemes

inferred← citeshttps://doi.org/10.1007/s00446-021-00398-3openalex-snapshot

A distributed algorithm for directed minimum-weight spanning tree

inferred← citeshttps://doi.org/10.1007/s00453-012-9647-1openalex-snapshot

How to Use Spanning Trees to Navigate in Graphs

inferred← citeshttps://doi.org/10.1007/s11036-024-02351-7openalex-snapshot

Hardware-Based Satellite Network Broadcast Storm Suppression Method

inferred← citeshttps://doi.org/10.1007/s11227-010-0484-1openalex-snapshot

A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs

inferred← citeshttps://doi.org/10.1007/s11721-012-0067-2openalex-snapshot

Distributed graph coloring: an approach based on the calling behavior of Japanese tree frogs

inferred← citeshttps://doi.org/10.1016/j.ifacol.2018.12.065openalex-snapshot

A Method for Distributed Transactive Control in Power Systems based on the Projected Consensus Algorithm

inferred← citeshttps://doi.org/10.1016/j.jcss.2021.11.006openalex-snapshot

Latency, capacity, and distributed minimum spanning trees

inferred← citeshttps://doi.org/10.1016/j.jpdc.2021.08.004openalex-snapshot

Improved distributed approximation for Steiner tree in the CONGEST model

inferred← citeshttps://doi.org/10.1016/j.tcs.2020.04.013openalex-snapshot

GHS algorithm on a graph with random weights

inferred← citeshttps://doi.org/10.1109/jsac.2009.090924openalex-snapshot

Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

inferred← citeshttps://doi.org/10.1109/pdgc.2016.7913120openalex-snapshot

Distributed minimum spanning tree based information exchange policy for distributed systems

inferred← citeshttps://doi.org/10.1109/sbrc.2014.17openalex-snapshot

Distributed and Autonomic Minimum Spanning Trees

inferred← citeshttps://doi.org/10.1109/sutc.2006.1636153openalex-snapshot

Ad-Hoc Routing Using Virtual Coordinates Based on Rooted Trees

inferred← citeshttps://doi.org/10.1109/sutc.2006.21openalex-snapshot

Ad-hoc routing using virtual coordinates based on rooted trees

inferred← citeshttps://doi.org/10.1109/tsipn.2023.3302658openalex-snapshot

Decentralized Eigendecomposition for Online Learning Over Graphs With Applications

inferred← citeshttps://doi.org/10.1137/090761549openalex-snapshot

Navigating in a Graph by Aid of Its Spanning Tree Metric

inferred← citeshttps://doi.org/10.1137/11085178xopenalex-snapshot

Distributed Verification and Hardness of Distributed Approximation

inferred← citeshttps://doi.org/10.1145/1248377.1248402openalex-snapshot

Local MST computation with short advice

inferred← citeshttps://doi.org/10.1145/1378533.1378569openalex-snapshot

Energy-optimal distributed algorithms for minimum spanning trees

inferred← citeshttps://doi.org/10.1145/1400751.1400787openalex-snapshot

Efficient distributed approximation algorithms via probabilistic tree embeddings

inferred← citeshttps://doi.org/10.1145/1542362.1542410openalex-snapshot

Distributed vision with smart pixels

inferred← citeshttps://doi.org/10.1145/1993636.1993686openalex-snapshot

Distributed verification and hardness of distributed approximation

inferred← citeshttps://doi.org/10.1145/2000807.2000814openalex-snapshot

Fast computation of small cuts via cycle space sampling

inferred← citeshttps://doi.org/10.1145/2499228openalex-snapshot

Towards a complexity theory for local distributed computing

inferred← citeshttps://doi.org/10.1145/2767386.2767405openalex-snapshot

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication

inferred← citeshttps://doi.org/10.1145/2933057.2933098openalex-snapshot

On Efficient Distributed Construction of Near Optimal Routing Schemes

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/3087801.3087827openalex-snapshot

Distributed MST and Routing in Almost Mixing Time

inferred← citeshttps://doi.org/10.1145/3087801.3087842openalex-snapshot

Brief Announcement

inferred← citeshttps://doi.org/10.1145/3146550openalex-snapshot

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks

inferred← citeshttps://doi.org/10.1145/3212734.3212737openalex-snapshot

Round- and Message-Optimal Distributed Graph Algorithms

inferred← citeshttps://doi.org/10.1145/3323165.3323195openalex-snapshot

Distributed Computation in Node-Capacitated Networks

inferred← citeshttps://doi.org/10.1145/3357713.3384298openalex-snapshot

Polylogarithmic-time deterministic network decomposition and distributed derandomization

inferred← citeshttps://doi.org/10.1145/3365005openalex-snapshot

A time- and message-optimal distributed algorithm for minimum spanning trees

inferred← citeshttps://doi.org/10.1145/3406325.3451081openalex-snapshot

Universally-optimal distributed algorithms for known topologies

inferred← citeshttps://doi.org/10.1145/3564246.3585201openalex-snapshot

Finding a Small Vertex Cut on Distributed Networks

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.1145/3816782.3819199openalex-snapshot

Near-Optimal Bounds for Adversarial Wake-up in Distributed Networks

inferred← citeshttps://doi.org/10.3929/ethz-a-005273546openalex-snapshot

Locality, Scheduling, and Selfishness: Algorithmic Foundations of Highly Decentralized Networks

inferred← citeshttps://doi.org/10.3929/ethz-b-000377526openalex-snapshot

Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

inferred← citeshttps://doi.org/10.48550/arxiv.1011.3049openalex-snapshot

Distributed Verification and Hardness of Distributed Approximation

inferred← citeshttps://doi.org/10.48550/arxiv.1602.02293openalex-snapshot

On Efficient Distributed Construction of Near Optimal Routing Schemes

inferred← citeshttps://doi.org/10.48550/arxiv.1802.01289openalex-snapshot

On Distributed Algorithms for Cost-Efficient Data Center Placement in Cloud Computing

inferred← citeshttps://doi.org/10.48550/arxiv.cs/0702113openalex-snapshot

Fast Computation of Small Cuts via Cycle Space Sampling

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.