Deterministic stateless centralized local algorithms for bounded degree graphs

DOI10.1007/978-3-662-44777-2_33MaRDI QIDQ2921425zbMATH OpenOpenAlexFDO

Authors Guy Even, Moti Medina, Dana Ron

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_33

zbMATH Keywords

graph algorithmssublinear approximation algorithmscentralized local algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Best of two local models: centralized local and distributed local algorithms
• Some simple distributed algorithms for sparse networks
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Deterministic distributed vertex coloring in polylogarithmic time
• Combinatorial algorithms for distributed graph coloring

Cited in

(17)

• Sampling and output estimation in distributed algorithms and LCAs
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Sublinear graph augmentation for fast query implementation
• Deterministic Decentralized Search in Random Graphs
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• New techniques and tighter bounds for local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• Non-local probes do not help with many graph problems
• Locally computing edge orientations
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Constant-time local computation algorithms
• Learning concepts definable in first-order logic with counting
• Local computation algorithms for spanners
• Improved dynamic graph coloring
• Local algorithms for sparse spanning graphs
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Local computation algorithms for graphs of non-constant degrees

This page was built for publication: Deterministic stateless centralized local algorithms for bounded degree graphs

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