An Improved Exact Algorithm for the Domatic Number Problem

Dr Holger Spakowski, University of Cape Town
Thursday 29 November 2007, 14h00, M 111 (Seminar Room)

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805^n, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta(G)>=5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems

Talks on Analog Computation

Prof Jeffery Zucker, McMaster University, Hamilton, Canada
Wednesday 30 May 2007, 16h00, M 111 (Seminar Room)
Thursday 31 May 2007, 13h00, M 111 (Seminar Room)

  • Talk 1: What is Analog Computation?
    Around the mid-20th century, it seemed that analog computation had been eclipsed by digital computation. However, in the last few decades there has been a resurgence of interest in analog computing. In this (non-technical) talk, I will discuss analog computation in general, and try to explain this resurgence of interest.

  • Talk 2: Fixed Point Semantics for Analog Networks
    In this talk, I will describe recent work by John Tucker (Swansea) and myself on fixed point semantics for analog networks of processors and channels containing streams of real numbers or other continuous data.

Note: Each talk is essentially self-contained, though there will be some cross-references.

Problems as Solutions

Dr Peter Schuster, University of Munich, Germany
Monday 19 March 2007, 15h00, M 111 (Seminar Room)

If a continuous function on a complete metric space has approximate roots and in a uniform manner at most one root, then it actually has a root. We validate this heuristic principle in Bishop-style constructive mathematics without countable choice, following Richman's way of defining the completion of a metric space as the set of all locations.