演講公告

新聞標題：　( 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.
  

go back