Minimal Restrained Domination Algorithms on Trees Using Dynamic Programming
- ASU Author/Contributor (non-ASU co-authors, if there are any, appear on document)
- Jeremy Booker (Creator)
- Institution
- Appalachian State University (ASU )
- Web Site: https://library.appstate.edu/
- Advisor
- Alice McRae
Abstract: In this paper we study a special case of graph domination, namely minimal restrained dominating sets on trees. A set S ? V is a dominating set if for every vertex u ? V-S, there exists v ? S such that uv ? E. A set S ? V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and another vertex in V-S. A restrained dominating set S is a minimal restrained dominating set if no proper subset of S is also a restrained dominating set. We give a dynamic programming style algorithm for generating largest minimal restrained dominating sets for trees and show that the decision problem for minimal restrained dominating sets is NP-complete for general graphs. We also consider independent restrained domination on trees and its associated decision problem for general graphs.
Minimal Restrained Domination Algorithms on Trees Using Dynamic Programming
PDF (Portable Document Format)
1434 KB
Created on 3/25/2014
Views: 2842
Additional Information
- Publication
- Thesis
- Booker, J. (2013). Minimal Restrained Domination Algorithms on Trees Using Dynamic Programming. Unpublished master’s thesis. Appalachian State University, Boone, NC.
- Language: English
- Date: 2013
- Keywords
- Graph domination, Restrained dominating sets on trees, Independent restrained dominating sets on trees , Minimal restrained dominating sets