演講公告
新聞標題: ( 2009-09-22 )
演講主題:Power domination problem in graphs
主講人:廖崇碩 博士(中研院資訊所)
演講日期:98年9月29日(星期二) <br>下午2:00 - 3:00
演講地點:(光復校區)科學一館223室
摘要內容:
The power utility network observation problem can be transformed into
the graph-theoretic power domination problem according to the
observation rules. A set S is a power dominating set (PDS) of a graph
G=(V,E), if every vertex and every edge in G are observed following
the observation rules of power system monitoring. The power domination
problem is to minimize the cardinality of a PDS of a graph.
Since a power dominating set has the capability of observing remote
elements via propagation, to the best of our knowledge, there are only
polynomial time algorithms for power domination problem in tree-type
graphs. We consider this combinatorial optimization problem in other
graph classes and would like to design efficient polynomial
algorithms. We present a linear time algorithm for finding the minimum
PDS of an interval graph, if the interval ordering of the graph is
provided, and show that the algorithm that runs in O(nlogn) time,
where n is the number of intervals, is asymptotically optimal, if the
interval ordering is not given. We also show that the same results
hold for the class of circular-arc graphs.
