Streaming Verification of Graph Properties.

DOI10.4230/LIPIcs.ISAAC.2016.3zbMath1398.68380arXiv1602.08162OpenAlexW2962941701MaRDI QIDQ4636484

Chitradeep Dutta Roy, Suresh Venkatasubramanian, Amirali Abdullah, Samira Daruki

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1602.08162

zbMATH Keywords

verificationmatchinggraph algorithmstravelling salesman problemstreaming interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Verifiable Stream Computation and Arthur--Merlin Communication

This page was built for publication: Streaming Verification of Graph Properties.