id: 05148476
dt: a
an: 05148476
au: Czygrinow, Andrzej; Hańćkowiak, Michał; Szymańska, Edyta
ti: Distributed approximation algorithms for planar graphs.
so: Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 6th Italian
    conference, CIAC 2006, Rome, Italy, May 29‒31, 2006. Proceedings.
    Berlin: Springer (ISBN 3-540-34375-X/pbk). Lecture Notes in Computer
    Science 3998, 296-307 (2006).
py: 2006
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/11758471_29
ab: Summary: In this paper we construct two distributed algorithms for
    computing approximations of a largest matching and a minimum dominating
    set in planar graphs on $n$ vertices. The approximation ratio in both
    cases approaches one with $n$ tending to infinity and the number of
    synchronous communication rounds is poly-logarithmic in $n$. Our
    algorithms are purely deterministic.
rv: