Tight bounds for distributed minimum-weight spanning tree verification (Q372968): Difference between revisions

← Older edit

@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 5999536
@@ Property / zbMATH Open document ID @@
+.68143
@@ Property / zbMATH Open document ID: 1230.68143 / rank @@
+Normal rank
@@ Property / DOI @@
+.4230/LIPIcs.STACS.2011.69
@@ Property / DOI: 10.4230/LIPIcs.STACS.2011.69 / rank @@
+Normal rank
@@ Property / publication date @@
+January 2012Timestamp +2012-01-23T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2012-01-23T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 23 January 2012 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+http://subs.emis.de/LIPIcs/frontdoor_7b9c.html
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+M14
@@ Property / Mathematics Subject Classification ID: 68M14 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+5999536
@@ Property / zbMATH DE Number: 5999536 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2006444174
@@ Property / OpenAlex ID: W2006444174 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04832
@@ Property / arXiv ID: 1512.04832 / rank @@
+Normal rank
@@ Property / cites work @@
+The local detection paradigm and its applications to self-stabilization
+Normal rank
@@ Property / cites work @@
+A trade-off between information and communication in broadcast protocols
+Normal rank
@@ Property / cites work @@
+Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
+Normal rank
@@ Property / cites work @@
+Eigenvalues of the natural random walk on the Burnside group \(B(3,n)\)
+Normal rank
@@ Property / cites work @@
+Distributed verification and hardness of distributed approximation
+Normal rank
@@ Property / cites work @@
+A tight unconditional lower bound on distributed randomwalk computation
+Normal rank
@@ Property / cites work @@
+Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
+Normal rank
@@ Property / cites work @@
+Optimal parallel verification of minimum spanning trees in logarithmic time
+Normal rank
@@ Property / cites work @@
+Memory requirements for silent stabilization
@@ Property / cites work: Memory requirements for silent stabilization / rank @@
+Normal rank
@@ Property / cites work @@
+Local Distributed Decision
@@ Property / cites work: Local Distributed Decision / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized distributed decision
@@ Property / cites work: Randomized distributed decision / rank @@
+Normal rank
@@ Property / cites work @@
+A Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+On the History of the Minimum Spanning Tree Problem
+Normal rank
@@ Property / cites work @@
+A randomized linear-time algorithm to find minimum spanning trees
+Normal rank
@@ Property / cites work @@
+Labeling Schemes for Flow and Connectivity
@@ Property / cites work: Labeling Schemes for Flow and Connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+A simpler minimum spanning tree verification algorithm
+Normal rank
@@ Property / cites work @@
+An optimal EREW PRAM algorithm for minimum spanning tree verification
+Normal rank
@@ Property / cites work @@
+Linear verification for spanning trees
@@ Property / cites work: Linear verification for spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed verification of minimum spanning trees
+Normal rank
@@ Property / cites work @@
+Proof labeling schemes
@@ Property / cites work: Proof labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Distributed Construction of Smallk-Dominating Sets and Applications
+Normal rank
@@ Property / cites work @@
+Sublinear bounds for randomized leader election
@@ Property / cites work: Sublinear bounds for randomized leader election / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed MST for constant diameter graphs
@@ Property / cites work: Distributed MST for constant diameter graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
+Normal rank
@@ Property / cites work @@
+An optimal minimum spanning tree algorithm
@@ Property / cites work: An optimal minimum spanning tree algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Applications of Path Compression on Balanced Trees
+Normal rank
@@ Property / cites work @@
+Q3707420
@@ Property / cites work: Q3707420 / rank @@
+Normal rank