Accueil

Qi Ge

  1. The Complexity of Counting Eulerian Tours in 4-Regular Graphs.

    Tue, 09/28/2010 - 15:01 — SomNambul
    Authors: Qi Ge, Daniel Stefankovic
    Subjects: Computational Complexity
    Abstract

    We investigate the complexity of counting Eulerian tours ({\sc #ET}) and its
    variations from two perspectives---the complexity of exact counting and the
    complexity w.r.t. approximation-preserving reductions (AP-reductions
    \cite{MR2044886}). We prove that {\sc #ET} is #P-complete even for planar
    4-regular graphs.

  2. A graph polynomial for independent sets of bipartite graphs.

    Thu, 11/26/2009 - 16:01 — SomNambul
    Authors: Qi Ge, Daniel Stefankovic
    Subjects: Discrete Mathematics
    Abstract

    We introduce a new graph polynomial that encodes interesting properties of
    graphs, for example, the number of matchings and the number of perfect
    matchings. Most importantly, for bipartite graphs the polynomial encodes the
    number of independent sets (#BIS).

Math-arch

Syndicate content