Approximate proof-labeling schemes

DOI10.1007/978-3-319-72050-0_5MaRDI QIDQ5915999zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Ami Paz, Mor Perry

Publication date 12 April 2018

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-72050-0_5

zbMATH Keywords

approximation algorithmsdistributed graph algorithmsdistributed verificationprimal-dual algorithms

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• Approximate proof-labeling schemes
• Proof labeling schemes
• Randomized proof-labeling schemes
• Randomized proof-labeling schemes
• Proof labeling schemes

Cited in

(11)

• Randomized proof-labeling schemes
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• Proof labeling schemes
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Local verification of global proofs
• Proof labeling schemes
• Approximate proof-labeling schemes
• Error-sensitive proof-labeling schemes
• Invited Paper: Reactive PLS for Distributed Decision
• Twenty-two new approximate proof labeling schemes

This page was built for publication: Approximate proof-labeling schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5915999)