Please use this identifier to cite or link to this item:
標題: Power Domination in Circular-arc Graphs
作者: Liao, Chung-Shou
關鍵字: Domination;Power domination;Interval graphs;Circular-arc graphs;Algorithm
出版社: Springer-Verlag
Project: Algorithmica, Volume�65, Issue�2, Page(s) �443-466.
A set S⊆V is a power dominating set (PDS) of a graph G=(V,E) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ(nlogn) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs.
ISSN: 0178-4617
DOI: 10.1007/s00453-011-9599-x
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.