Non-local probes do not help with many graph problems
From MaRDI portal
Publication:1660935
DOI10.1007/978-3-662-53426-7_15zbMath1393.68051arXiv1512.05411OpenAlexW2218566908MaRDI QIDQ1660935
Moti Medina, Jukka Suomela, Reut Levi, Juho Hirvonen, Mika Göös
Publication date: 16 August 2018
Full work available at URL: https://arxiv.org/abs/1512.05411
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Can we locally compute sparse connected subgraphs?, Unnamed Item, Constant-time local computation algorithms, Fast distributed algorithms for testing graph properties, Best of two local models: centralized local and distributed local algorithms
