Dominating Sets in Two-Directional Orthogonal Ray Graphs

Asahi TAKAOKA  Satoshi TAYU  Shuichi UENO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.8   pp.1592-1595
Publication Date: 2015/08/01
Publicized: 2015/05/08
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDL8068
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
Boolean-width,  dominating set,  dynamic programming,  two-directional orthogonal ray graphs,  

Full Text: PDF>>
Buy this Article




Summary: 
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.