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)
Content information:
Item Type: Paper (Technical Report)
Citations: 45 (Google Scholar) |
Uncontrolled Keywords: exact algorithms domination connected domination edge domination maximum leaf spanning tree 3-colourability
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms > 68W01 General

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C69 Dominating sets, independent sets, cliques

  • 68-XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C15 Coloring of graphs and hypergraphs

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Speckenmeyer
    Related URLs:
    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