A Note on Two-Directional Orthogonal Ray Graphs and Related Graphs
スポンサーリンク
概要
- 論文の詳細を見る
An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the plane. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. An orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction and every vertical ray has the same direction. We derive some structural properties of these graphs, and show that the (weighted) dominating set problem can be solved in polynomial time for 2-directional orthogonal ray graphs. We also show that the induced matching problem and the strong edge coloring problem can be solved in polynomial time for 3-directional orthogonal ray graphs. Moreover, we show a quadratic time recognition algorithm for interval bigraphs, a special kind of 2-directional orthogonal ray graphs.
- 2013-10-30
著者
-
Satoshi Tayu
Department Of Communications And Integrated Systems Tokyo Institute Of Technology
-
Asahi Takaoka
Department of Communications and Integrated Systems, Tokyo Institute of Technology
-
Shuichi Ueno
Department of Communications and Computer Engineering, Tokyo Institute of Technology
-
Shuichi Ueno
Department of Communications and Computer Engineering Tokyo Institute of Technology
-
Asahi Takaoka
Department of Communications and Computer Engineering, Tokyo Institute of Technology
-
Shuichi Ueno
Department of Communication and Computer Engineering, Tokyo Institute of Technology
関連論文
- On Two-Directional Orthogonal Ray Graphs
- Representation of Bipartite Graphs by OBDDs
- A Note on Two-Directional Orthogonal Ray Graphs and Related Graphs
- [招待講演]Orthogonal Ray Graphs with Applications to Nanocircuit Design
- Stable Matchings in Trees