Efficiency in exponential time for domination-type problems

作     者：Schiermeyer, Ingo 

作者机构：TU Bergakad Freiberg Inst Diskrete Math & Algebra D-09596 Freiberg Germany 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2008年第156卷第17期

页      面：3291-3297页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Parts of this research were performed within the RIP program at the Mathematisches Forschungsinstitut Oberwolfach. Hospitality and financial support is gratefully acknowledged 

主　　题：Exact algorithms Domination Matching technique 

摘      要：We design fast exponential time algorithms for some intractable graph-theoretic problems. Our main result states that a minimum optional dominating set in a graph of order n can be found in time 0* (1.8899(n)). Our methods to obtain this result involve matching techniques. The list of the considered problems includes MINIMUM MAXIMAL MATCHING, 3-COLOURABILITY, MINIMUM DOMINATING EDGE SET, MINIMUM CONNECTED DOMINATING SET (similar to MAXIMUM LEAF SPANNING TREE), MINIMUM INDEPENDENT DOMINATING SET and MINIMUM DOMINATING SET. (C) 2008 Elsevier B.V. All rights reserved.