For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Dominating Sets in Two-Directional Orthogonal Ray Graphs
Asahi TAKAOKA Satoshi TAYU Shuichi UENO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/08/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Boolean-width, dominating set, dynamic programming, two-directional orthogonal ray graphs,
Full Text: PDF>>
A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.