Converting Online Algorithms to Local Computation Algorithms

DOI10.1007/978-3-642-31594-7_55zbMath1272.68471arXiv1205.1312OpenAlexW2112551191MaRDI QIDQ2843290

Yishay Mansour, Shai Vardi, Aviad Rubinstein, Ning Xie

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (11)

New techniques and tighter bounds for local computation algorithms ⋮ Can we locally compute sparse connected subgraphs? ⋮ Average Sensitivity of Graph Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constructing near spanning trees with few local inspections ⋮ Constant-time local computation algorithms ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Local algorithms for sparse spanning graphs

This page was built for publication: Converting Online Algorithms to Local Computation Algorithms