Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.10 No.4, pp.549-568 (December 1994)
Polynomial Algorithms for Weighted
Perfect Domination Problems on Interval and
Circular-Arc Graphs*

Maw-Shang Chang and Yi-Chang Liu
Department of Computer Science and Information Engineering
National Chung Cheng University
Min-Hsiung, Chiayi 621, Taiwan
Republic of China

This paper gives a unified approach to the design of linear time algorithms for the weighted perfect domination problem and its three variants on interval graphs. The results are then extended to solve the same problems on circular-arc graphs in O(|E| |V| + |V|2) time, where VM and E are the vertex set and edge set of the given graph, respectively.

Keywords: interval graphs, circular-arc graphs, perfect domination, graph algorithms. AMS(MOS) subject classfications. 05C85, 68Q25, 68Q20, 68R10, 90C27

Received November 19, 1993; revised August 15, 1994.
Communicated by Jhing-Fa Wang.
*Supported partly by the National Science Council of the Republic of China under grant NSC 83-0208-M-194-029.