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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.