| 大会名称 |
|---|
| 2018年 総合大会 |
| 大会コ－ド |
| 2018G |
| 開催年 |
| 2018 |
| 発行日 |
| セッション番号 |
| A-1 |
| セッション名 |
| 回路とシステム |
| 講演日 |
| 2018/3/23 |
| 講演場所(会議室等) |
| ２号館 7Ｆ 2703教室 |
| 講演番号 |
| A-1-19 |
| タイトル |
| A Matching Algorithm for 2-Directional Orthogonal Ray Graphs |
| 著者名 |
| ○Ryu Sugimoto, Satoshi Tayu, Shuichi Ueno, |
| キーワード |
| maximum matching, orthogonal ray graph, algorithm |
| 抄録 |
| A bigraph with a bipartition (U,V) is called an orthogonal ray graph if there exist a set of disjoint horizontal rays Ru, u ∈ U, in the xy-plane, and a set of disjoint vertical rays Rv, v ∈ V, such that for any u ∈ U and v ∈ V, (u, v) ∈ E(G) if and only if Ru and Rv intersect. A set M of edge of a graph is called a matching if no two edges in M have a common endvertex. This paper shows an O(n2) algorithm to obtain a maximum matching of a 2-directional orthogonal ray graph with n vertices. |
| 本文pdf |
|
PDF download
|