Best of two local models: Centralized local and distributed local algorithms
| Autor: | Dana Ron, Moti Medina, Guy Even |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Matching (graph theory)
Computer science Model of computation 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Computer Science Applications Theoretical Computer Science Vertex (geometry) Computational Theory and Mathematics 010201 computation theory & mathematics Distributed algorithm 020204 information systems Bounded function 0202 electrical engineering electronic engineering information engineering Maximal independent set Algorithm Information Systems |
| Zdroj: | Information and Computation. 262:69-89 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2018.07.001 |
| Popis: | We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in log ⁎ n , where n is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak (FOCS 2008) is employed to obtain a distributed approximation scheme for maximum (weighted) matching. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect