Valentin Polishchuk

  1. Local algorithms in (weakly) coloured graphs.

    Authors: Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto
    Subjects: and Cluster Computing, Distributed, Parallel
    Abstract

    A local algorithm is a distributed algorithm that completes after a constant
    number of synchronous communication rounds. We present local approximation
    algorithms for the minimum dominating set problem and the maximum matching
    problem in 2-coloured and weakly 2-coloured graphs. In a weakly 2-coloured
    graph, both problems admit a local algorithm with the approximation factor
    $(\Delta+1)/2$, where $\Delta$ is the maximum degree of the graph. We also give
    a matching lower bound proving that there is no local algorithm with a better
    approximation factor for either of these problems.

RSS-материал