Local algorithms for graphs

DOI10.1093/ACPROF:OSO/9780198743736.003.0008MaRDI QIDQ2990203zbMATH OpenOpenAlexFDO

Authors David Gamarnik

Publication date 29 July 2016

Published in Statistical Physics, Optimization, Inference, and Message-Passing Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph modelsindependent set problemlocal algorithmssparse random graphstree-like graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We are going to analyze local algorithms over sparse random graphs. These algorithms are based on local information where local regards to a decision made by the exploration of a small neighbourhood of a certain vertex plus a believe of the structure of the whole graph and maybe added some randomness. This kind of algorithms can be a natural response to the given problem or an efficient approximation such as the Belief Propagation Algorithm.

Recommendations

• Limits of local algorithms over sparse random graphs
• Limits of local algorithms over sparse random graphs
• scientific article; zbMATH DE number 3902710
• Survey of local algorithms
• Local algorithms for block models with side information

Cited in

(14)

• Local algorithms on graphs
• An efficient algorithm to recognize locally equivalent graphs
• On the recognition of families of graphs with local computations
• Local algorithms for block models with side information
• Local update algorithms for random graphs
• Limits of local algorithms over sparse random graphs
• scientific article; zbMATH DE number 3902710 (Why is no real title available?)
• scientific article; zbMATH DE number 3853143 (Why is no real title available?)
• Local structure theorems for Erdős-Rényi graphs and their algorithmic applications
• Local algorithms for sparse spanning graphs
• Survey of local algorithms
• Node and edge averaged complexities of local graph problems
• Local Graph Exploration and Fast Property Testing
• Localization of edges in graph models of two-level algorithms

This page was built for publication: Local algorithms for graphs

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