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

centralized local algorithmsgraph algorithmssublinear approximation algorithms

Mathematics Subject Classification ID

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

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)

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

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)