Fast distributed algorithms for testing graph properties (Q5915702): Difference between revisions

← Older edit

@@ description / en / description / en @@
-scientific article; zbMATH DE number 6919228
+scientific article; zbMATH DE number 7040099
@@ Property / zbMATH Open document ID @@
+.68369
@@ Property / zbMATH Open document ID: 1428.68369 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/s00446-018-0324-8
@@ Property / DOI: 10.1007/s00446-018-0324-8 / rank @@
+Normal rank
@@ Property / published in @@
+Distributed Computing
@@ Property / published in: Distributed Computing / rank @@
+Normal rank
@@ Property / publication date @@
+March 2019Timestamp +2019-03-21T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2019-03-21T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 21 March 2019 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+7040099
@@ Property / zbMATH DE Number: 7040099 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2789477538
@@ Property / OpenAlex ID: W2789477538 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.03718
@@ Property / arXiv ID: 1602.03718 / rank @@
+Normal rank
@@ Property / cites work @@
+Many Random Walks Are Faster Than One
@@ Property / cites work: Many Random Walks Are Faster Than One / rank @@
+Normal rank
@@ Property / cites work @@
+Testing Triangle-Freeness in General Graphs
@@ Property / cites work: Testing Triangle-Freeness in General Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Testing <i>k</i>-colorability
@@ Property / cites work: Testing <i>k</i>-colorability / rank @@
+Normal rank
@@ Property / cites work @@
+A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
+Normal rank
@@ Property / cites work @@
+Distributedly Testing Cycle-Freeness
@@ Property / cites work: Distributedly Testing Cycle-Freeness / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized Proof-Labeling Schemes
@@ Property / cites work: Randomized Proof-Labeling Schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Testing properties of directed graphs: acyclicity and connectivity*
+Normal rank
@@ Property / cites work @@
+Self-testing/correcting with applications to numerical problems
+Normal rank
@@ Property / cites work @@
+Distributed discovery of large near-cliques
@@ Property / cites work: Distributed discovery of large near-cliques / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic methods in the congested clique
@@ Property / cites work: Algebraic methods in the congested clique / rank @@
+Normal rank
@@ Property / cites work @@
+The strong perfect graph theorem
@@ Property / cites work: The strong perfect graph theorem / rank @@
+Normal rank
@@ Property / cites work @@
+“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
+Normal rank
@@ Property / cites work @@
+The communication complexity of distributed task allocation
+Normal rank
@@ Property / cites work @@
+On the power of the congested clique model
@@ Property / cites work: On the power of the congested clique model / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Theory and Probability
@@ Property / cites work: Graph Theory and Probability / rank @@
+Normal rank
@@ Property / cites work @@
+Q4598260
@@ Property / cites work: Q4598260 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4668732
@@ Property / cites work: Q4668732 / rank @@
+Normal rank
@@ Property / cites work @@
+Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
+Normal rank
@@ Property / cites work @@
+Distributed MST and Routing in Almost Mixing Time
@@ Property / cites work: Distributed MST and Routing in Almost Mixing Time / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing and its connection to learning and approximation
+Normal rank
@@ Property / cites work @@
+A sublinear bipartiteness tester for bounded degree graphs
+Normal rank
@@ Property / cites work @@
+Property testing in bounded degree graphs
@@ Property / cites work: Property testing in bounded degree graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Aspects of Property Testing in the Dense Graphs Model
+Normal rank
@@ Property / cites work @@
+Three theorems regarding testing graph properties
@@ Property / cites work: Three theorems regarding testing graph properties / rank @@
+Normal rank
@@ Property / cites work @@
+Non-local probes do not help with many graph problems
+Normal rank
@@ Property / cites work @@
+Large cuts with local algorithms on triangle-free graphs
+Normal rank
@@ Property / cites work @@
+Optimal distributed all pairs shortest paths and applications
+Normal rank
@@ Property / cites work @@
+Triangle Finding and Listing in CONGEST Networks
@@ Property / cites work: Triangle Finding and Listing in CONGEST Networks / rank @@
+Normal rank
@@ Property / cites work @@
+Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
+Normal rank
@@ Property / cites work @@
+Tight Bounds for Testing Bipartiteness in General Graphs
+Normal rank
@@ Property / cites work @@
+Proof labeling schemes
@@ Property / cites work: Proof labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient distributed source detection with limited bandwidth
+Normal rank
@@ Property / cites work @@
+Probability and Computing
@@ Property / cites work: Probability and Computing / rank @@
+Normal rank
@@ Property / cites work @@
+Testing the diameter of graphs
@@ Property / cites work: Testing the diameter of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Distributed coloring algorithms for triangle-free graphs
+Normal rank
@@ Property / cites work @@
+Q3615896
@@ Property / cites work: Q3615896 / rank @@
+Normal rank
@@ Property / cites work @@
+lgorithmic and Analysis Techniques in Property Testing
+Normal rank
@@ Property / cites work @@
+Robust Characterizations of Polynomials with Applications to Program Testing
+Normal rank
@@ Property / cites work @@
+Distributed Verification and Hardness of Distributed Approximation
+Normal rank
@@ Property / cites work @@
+Distributed Random Walks
@@ Property / cites work: Distributed Random Walks / rank @@
+Normal rank