理論計算機科学講演会のお知らせ
次のように講演会を開催します。ご興味をお持ちの方のご参加をお待ち申し上げます。
日時：６月９日（水）14:00-16:00 場所：IB電子情報館北５階 電気系会議室 講演題目：Power Domination Problems in Graphs 講演者：D. T. Lee
Institute of Information Sience
Academia Sinica, Nankang, Taipei, Taiwan内容梗概：
We consider a variation of graph-theoretic domination problem that arises in monitoring an electric power system of its voltage and current states at loads and branches of the power system respectively. To monitor or observe an electric power system by placing as few phase measurement units (PMUs) as possible is closely related to the famous vertex cover problem and domination problem in graph theory. A set S is a power dominating set (PDS) of a graph G=(V,E), if every vertex and every edge in the system are observed following the observation rules of power system monitoring. The minimum cardinality of a PDS of a graph G is the power domination number of G.
We shall show that the problem of finding the power domination number for split graphs, a subclass of chordal graphs, is NP-complete. We thus consider this problem for a subclass of chordal graphs, i.e., interval graphs, Specifically we shall present a linear time algorithm for finding the minimum PDS of an interval graph, if the interval model of the graph is provided and the endpoints of the intervals are given sorted. We also extend the result to the class of proper circular-arc graphs and conjecture that the power domination problem in general circular-arc graphs can be solved in linear time. Some open problems will be given in this presentation.
問い合わせ先：
平田富夫
名古屋大学大学院情報科学研究科計算機数理科学専攻
464-8603 名古屋市千種区不老町
TEL: 052 789 2725
FAX: 052 789 3089
Email: hirata@is.nagoya-u.ac.jp