| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419837 | Discrete Applied Mathematics | 2008 | 7 Pages |
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 nn can be found in time O∗(1.8899n)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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ingo Schiermeyer,