文章基本信息

标题：A New Approach to Find Minimal Dominating Set of an Interval Graph
本地全文：下载
作者：Arnab Kumar Das ; Dr Bichitra Kalita
期刊名称：International Journal of Computer Science and Information Technologies
电子版ISSN：0975-9646
出版年度：2018
卷号：9
期号：2
页码：27-30
出版社：TechScience Publications
摘要：The problem of finding a minimal dominating set orexternally stable set in a graph is a classical NP completeproblem in computational complexity theory. Till now there isno efficient algorithm that finds a smallest dominating set fora given graph. Several greedy algorithms have been proposedto find the minimal dominating set on a special class of graphcalled interval graph. Interval graphs are very important infinding combinatorial structures and various applicationshave been found in different fields. In this paper the problemof computing minimum dominating sets of n intervals on thereal lines have been studied. A new algorithm is proposedwhich will produce solutions of finding dominating set whichare optimal up to a certain factor.
关键词：Interval graph; Dominating set; Minimal;dominating set;