Главная

Charilaos Efthymiou

  1. A simple algorithm for random colouring G(n, d/n) using (2+\epsilon)d colours.

    Ср, 07/06/2011 - 15:01 — SomNambul
    Authors: Charilaos Efthymiou
    Subjects: Discrete Mathematics
    Abstract

    Approximate random k-colouring of a graph G=(V,E) is a very well studied
    problem in computer science and statistical physics. It amounts to constructing
    a k-colouring of G which is distributed close to Gibbs distribution, i.e. the
    uniform distribution over all the k-colourings of G. Here, we deal with the
    problem when the underlying graph is an instance of Erdos-Renyi random graph
    G(n,p), where p=d/n and d is fixed.

  2. Deterministic counting of graph colourings using sequences of subgraphs.

    Чт, 10/01/2009 - 00:35 — SomNambul
    Authors: Charilaos Efthymiou
    Subjects: Discrete Mathematics
    Abstract

    In this paper we propose a deterministic algorithm for approximate counting
    the $k$-colourings of a graph. We consider two categories of graphs. The first
    one is the sparse random graphs $G_{n,d/n}$, where each edge is chosen
    independently with probability $d/n$ and $d$ is fixed. The second one is a
    family we call {\em locally $\alpha$-dense graphs} of bounded maximum degree
    \Delta.

Math-arch

RSS-материал