Efficiency in exponential time for domination-type problems |
| |
Authors: | Ingo Schiermeyer |
| |
Institution: | Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, D-09596 Freiberg, Germany |
| |
Abstract: | 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 O∗(1.8899n). 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 (∼Maximum Leaf Spanning Tree), Minimum Independent Dominating Set and Minimum Dominating set. |
| |
Keywords: | Exact algorithms Domination Matching technique |
本文献已被 ScienceDirect 等数据库收录! |
|