
For FullText 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 and Induced Matchings in Orthogonal Ray Graphs
Asahi TAKAOKA Satoshi TAYU Shuichi UENO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E97D
No.12
pp.31013109 Publication Date: 2014/12/01 Publicized: 2014/09/09 Online ISSN: 17451361
DOI: 10.1587/transinf.2014EDP7184 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: booleanwidth, dominating set, induced matching, orthogonal ray graphs, strong edge coloring,
Full Text: PDF>>
Summary:
An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed halflines) in the plane. Such a graph is 3directional if every vertical ray has the same direction, and 2directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomialtime algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2directional orthogonal ray graphs, the dominating set problem can be solved in O(n^{2} log^{5} n) time, the weighted dominating set problem can be solved in O(n^{4} log n) time, and the number of dominating sets of a fixed size can be computed in O(n^{6} log n) time, where n is the number of vertices in the graph. We also show that for 2directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n^{2}+m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3directional orthogonal ray graphs, the induced matching problem can be solved in O(m^{2}) time, the weighted induced matching problem can be solved in O(m^{4}) time, and the strong edge coloring problem can be solved in O(m^{3}) time. We finally show that the weighted induced matching problem can be solved in O(m^{6}) time for orthogonal ray graphs.

