Distributed verification of minimum spanning trees

No abstract is available for this paper.

• Publication year

  2006

• Venue

  ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

• Publication date

  2006-07-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00446-007-0025-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Proof labeling schemes

  2005influential reference
• Compact and localized distributed data structures

  2003cited by this paper
• Constant-time distributed dominating set approximation

  2003cited by this paper
• What Can Be Computed Locally ?

  2003cited by this paper
• Labeling schemes for flow and connectivity

  2002cited by this paper
• Distance labeling in graphs

  2001cited by this paper
• Approximate Distance Labeling Schemes

  2001influential reference
• An optimal minimum spanning tree algorithm

  2000cited by this paper
• Fast Distributed Construction of Small k-Dominating Sets and Applications

  1998cited by this paper
• An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification

  1997cited by this paper
• Uniform Dynamic Self-Stabilizing Leader Election

  1997cited by this paper
• The complexity of crash failures

  1997cited by this paper
• The Local Detection Paradigm and Its Application to Self-Stabilization

  1997cited by this paper
• Crash failures can drive protocols to arbitrary states

  1996cited by this paper
• Memory requirements for silent stabilization

  1996cited by this paper
• Protocol Independent Multicast (PIM): Motivation and Architecture

  1995cited by this paper
• A simpler minimum spanning tree verification algorithm

  1995influential reference
• A distributed control architecture of high-speed networks

  1995cited by this paper
• A randomized linear-time algorithm to find minimum spanning trees

  1995cited by this paper
• Distributed Reset

  1994cited by this paper
• Optimal parallel verification of minimum spanning trees in logarithmic time

  1994influential reference
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

  1994cited by this paper
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

  1992influential reference
• Implicit representation of graphs

  1992cited by this paper
• Distributed program checking: a paradigm for building self-stabilizing distributed protocols

  1991cited by this paper
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

  1990cited by this paper
• A linear algorithm for finding dominators in flow graphs and related problems

  1985cited by this paper
• Linear verification for spanning trees

  1984cited by this paper
• Data structures and network algorithms

  1983cited by this paper
• A Distributed Algorithm for Minimum-Weight Spanning Trees

  1983influential reference
• Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees

  1982influential reference
• Applications of Path Compression on Balanced Trees

  1979influential reference
• Some complexity questions related to distributive computing(Preliminary Report)

  1979cited by this paper
• [93] Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM.

  year unknowncited by this paper

• Proving there is a leader without naming it

  2025cites this paper
• A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs

  2025cites this paper
• Fully Local Succinct Distributed Arguments

  2024cites this paper
• Near-Optimal Resilient Labeling Schemes

  2024cites this paper
• Shared Versus Private Randomness in Distributed Interactive Proofs

  2024cites this paper
• Decreasing verification radius in local certification

  2024cites this paper
• Distributed Computation with Local Advice

  2024cites this paper
• Tight bounds on the message complexity of distributed tree verification

  2024cites this paper
• On Polynomial Time Local Decision

  2023cites this paper
• Distributed Certification for Classes of Dense Graphs

  2023cites this paper
• Lower bound for constant-size local certification

  2022cites this paper
• Locally Restricted Proof Labeling Schemes (Full Version)

  2022cites this paper
• Local Certification of Reachability

  2022cites this paper
• An Almost Singularly Optimal Asynchronous Distributed MST Algorithm

  2022cites this paper
• Local Mending

  2021influential citation
• Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators

  2021cites this paper
• Stabilization, Safety, and Security of Distributed Systems: 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18–21, 2020, Proceedings

  2020influential citation
• Twenty-Two New Approximate Proof Labeling Schemes

  2020cites this paper
• Shared vs Private Randomness in Distributed Interactive Proofs

  2020cites this paper
• Trade-offs in Distributed Interactive Proofs

  2019cites this paper
• Memory Lower Bounds for Self-Stabilization

  2019cites this paper
• Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

  2019cites this paper
• Memory lower bounds for deterministic self-stabilization.

  2019cites this paper
• Introduction to local certification

  2019influential citation
• Brief Announcement: Memory Lower Bounds for Self-Stabilization

  2019cites this paper
• Note on distributed certification of minimum spanning trees

  2019cites this paper
• Vérification de preuves distribuées : compromis temps-espace

  2019cites this paper
• Silent MST approximation for tiny memory

  2019cites this paper
• The Power of Distributed Verifiers in Interactive Proofs

  2018cites this paper
• Local checkability, no strings attached: (A)cyclicity, reachability, loop free updates in SDNs

  2018cites this paper
• Local certification in distributed computing: error-sensitivity, uniformity, redundancy, and interactivity. (Certification locale en calcul distribué : sensibilité aux erreurs, uniformité, redondance et interactivité)

  2018cites this paper
• 24 : 2 Redundancy in Distributed Proofs 1 Introduction 1 . 1

  2018cites this paper
• Local verification of global proofs

  2018cites this paper
• Redundancy in distributed proofs

  2018influential citation
• Interactive Distributed Proofs

  2018cites this paper
• Error-Sensitive Proof-Labeling Schemes

  2017influential citation
• Towards a Complexity Theory for the Congested Clique

  2017cites this paper
• Proof-Labeling Schemes: Broadcast, Unicast and in Between

  2017cites this paper
• Approximate Proof-Labeling Schemes

  2017cites this paper
• The ANTS problem

  2016cites this paper
• An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

  2016cites this paper
• Space-Time Tradeoffs for Distributed Verification

  2016cites this paper
• Survey of Distributed Decision

  2016cites this paper
• A hierarchy of local decision

  2016influential citation
• Local checkability, no strings attached

  2016cites this paper
• Distributed Alarming in the On-Duty and Off-Duty Models

  2016cites this paper
• Locally Checkable Proofs in Distributed Computing

  2016influential citation
• Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees

  2015influential citation
• Randomized proof-labeling schemes

  2015influential citation
• Fast and Compact Distributed Verification and Self-stabilization of a DFS Tree

  2014influential citation
• Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction

  2014cites this paper
• A new algorithm for the minimum spanning tree verification problem

  2014cites this paper
• On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms

  2014influential citation
• A Bibliography of Local Algorithms

  2014cites this paper
• Construction auto-stabilisante silencieuse optimale en mémoire d'arbres couvants de degré minimum

  2014influential citation
• What can be decided locally without identifiers?

  2013cites this paper
• Exploiting locality in distributed SDN control

  2013cites this paper
• Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

  2013cites this paper
• Towards a complexity theory for local distributed computing

  2013cites this paper
• On the Design, Analysis, and Implementation of Algorithms for Selected Problems in Graphs and Networks

  2013cites this paper
• Locally Checkable Proofs ∗

  2013cites this paper
• Stabilization, Safety, and Security of Distributed Systems

  2013influential citation
• Survey of local algorithms

  2013cites this paper
• Local Decision and Verification with Bounded-Size Outputs

  2013cites this paper
• Distributed Verification Using Mobile Agents

  2013cites this paper
• Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology

  2012cites this paper
• On the Impact of Identifiers on Local Decision

  2012cites this paper
• Randomized distributed decision

  2012cites this paper
• A note on labeling schemes for graph connectivity

  2012cites this paper
• Distributed Decision Problems: The Locality Angle

  2011cites this paper
• Graph and geometric algorithms on distributed networks and databases

  2011cites this paper
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST

  2011influential citation
• Toward more localized local algorithms: removing assumptions concerning global knowledge

  2011cites this paper
• Algorithmes auto-stabilisants pour la construction d'arbres couvrants et la gestion d'entités autonomes. (Self-stabilizing algorithms for spanning tree construction and for the management of mobile entities)

  2011cites this paper
• Tight Bounds For Distributed MST Verification

  2011cites this paper
• Toward More Localized Local Algorithms: Removing Assumptions Concerning Global Knowledge (Extended Abstract)

  2011cites this paper
• Compact ancestry labeling schemes for XML trees

  2010cites this paper
• Distributed verification and hardness of distributed approximation

  2010cites this paper
• Local Distributed Decision

  2010cites this paper
• An optimal ancestry scheme and small universal posets

  2010cites this paper
• Fast Self-stabilizing Minimum Spanning Tree Construction - Using Compact Nearest Common Ancestor Labeling Scheme

  2010cites this paper
• Online computation with advice

  2009cites this paper
• An Optimal Labeling for Node Connectivity

  2009cites this paper
• Compact Ancestry Labeling Schemes for Trees of Small Depth

  2009cites this paper
• An Optimal Labeling Scheme for Ancestry Queries

  2009cites this paper
• A note on models for graph representations

  2009cites this paper
• Controller and estimator for dynamic networks

  2007cites this paper
• Local MST Computation with Short Advice

  2007cites this paper
• Labeling schemes for vertex connectivity

  2007cites this paper
• Constructing Labeling Schemes through Universal Matrices

  2006cites this paper
• On Distributed Verification

  2006influential citation
• General compact labeling schemes for dynamic trees

  2005cites this paper
• Proof labeling schemes

  2005cites this paper
• D C ] 2 0 Se p 20 17 Survey of Distributed Decision ∗ †

  year unknowncites this paper
• Energy-Efficient Distributed Computing

  year unknowncites this paper