Distributed verification of minimum spanning trees
type: Item
instance of: scholarly article
title: Distributed verification of minimum spanning trees
zbMATH Open document ID: 1266.68217
author: Amos Korman
author: Shay Kutten
published in: Distributed Computing
publication date: 2013-06-20T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6177658
zbMATH Keywords: network algorithms
zbMATH Keywords: graph property verification
zbMATH Keywords: labeling schemes
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: proof labeling schemes
zbMATH Keywords: self stabilization
MaRDI profile type: Publication
full work available at URL: s00446-007-0025-1
OpenAlex ID: W2023425290
cites work: The local detection paradigm and its applications to self-stabilization
cites work: Distributed reset
cites work: A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
cites work: Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
cites work: Optimal parallel verification of minimum spanning trees in logarithmic time
cites work: Memory requirements for silent stabilization
cites work: Q4535803
cites work: Trans-dichotomous algorithms for minimum spanning trees and shortest paths
cites work: A Distributed Algorithm for Minimum-Weight Spanning Trees
cites work: Q4796196
cites work: Distance labeling in graphs (extended abstract)
cites work: The complexity of crash failures
cites work: Crash failures can drive protocols to arbitrary states
cites work: Implicat Representation of Graphs
cites work: Q4829032
cites work: A randomized linear-time algorithm to find minimum spanning trees
cites work: Linear verification for spanning trees
cites work: Proof labeling schemes
cites work: Fast Distributed Construction of Smallk-Dominating Sets and Applications
cites work: A simpler minimum spanning tree verification algorithm
cites work: An optimal EREW PRAM algorithm for minimum spanning tree verification
cites work: Constant-time distributed dominating set approximation
cites work: What cannot be computed locally!
cites work: What Can be Computed Locally?
cites work: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
cites work: Q3707420
cites work: Applications of Path Compression on Balanced Trees
DOI: 10.1007/S00446-007-0025-1
description: scientific article; zbMATH DE number 6177658