Weighted dominating sets and induced matchings in orthogonal ray graphs
Asahi Takaoka, Satoshi Tayu, Shuichi Ueno · 2014
An orthogonal ray graph is a graph such that for each vertex, there exists an axis-parallel rays (closed half-lines) in the plane, and two vertices are adjacent if and only if the corresponding rays intersect. A 2-directional orthogonal ray graph is an orthogonal ray graph such that the corresponding ray of each vertex is a rightward ray or a downward ray. We recently showed in [12] that the weighted dominating set problem can be solved in O(n4log n) time for vertex-weighted 2-directional orthogonal ray graphs by using a new parameter, boolean-width of graphs, where n is the number of vertices in a graph. We improve the result by showing an O(n3)-time algorithm to solve the problem, based on a direct dynamic programming approach. We also show that the weighted induced matching problem can be solved in O(m6) time for edge-weighted orthogonal ray graphs, where m is the number of edges in a graph, closing the gap posed in [12].