Exact algorithms for MINIMUM DOMINATING SET

Randerath, Bert and Schiermeyer, Ingo (2004) Exact algorithms for MINIMUM DOMINATING SET.
Technical Report , 8 p.

Abstract

We design exact algorithms for several NP-complete graph-theoretic problems. The term exact algorithm is a shorthand for a fast exponential time algorithm. Our main result states that a minimum dominating set in a graph of order n can be found in time O(1.8899^n). The list of considered problems includes MINIMUM DOMINATING SET, 3-COLOURABILITY, MINIMUM CONNECTED DOMINATING SET (~MAXIMUM LEAF SPANNING TREE), MINIMUM EDGE DOMINATING SET, MINIMUM INDEPENDENT DOMINATING SET and MINIMUM MAXIMAL MATCHING.


Actions:
Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-469
Depositing User: Bert Randerath
Date Deposited: 27 Apr 2004 00:00
Last Modified: 12 Aug 2011 14:28
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/469