
An orthogonal ray graph is a graph such that for each vertex, there exists an axis-parallel rays (closed halflines) 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(n4 log 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].
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
