[招待講演]Orthogonal Ray Graphs with Applications to Nanocircuit Design

概要

論文の詳細を見る
A bipartite graph (bigraph) G with a bipartition (U,V) is called an orthogonal ray graph (ORG) if there exist a family of non-intersecting rays (half-lines) Ru, u ∈U, parallel to the x-axis in the xy-plane, and a family of non-intersecting rays Rv, v ∈ V, parallel to the y-axis such that for any u ∈ U and v ∈ V, (u, v) ∈ E (G) if and only if Ru and Rv intersect. An ORG G is called a 3-directional orthogonal ray graph (3-DORG) if every Ru, u ∈ U has the same direction. An ORG G is called a 2-directional orthogonal ray graph (2-DORG) if every Ru, u ∈ U has the same direction, and every Rv, v ∈ V has the same direction. The ORG was introduced in connection with defect tolerance schemes for nano-programmable logic arrays (nano-PLAs). We consider two fundamental problems on nano-PLA design, the logic mapping problem and the problem of finding a largest defect-free sub-crossbar. The problems are formulated as the subgraph isomorphism problem and the biclique problem for ORGs. We review the complexity of the problems. We next review some properties of ORGs, and various characterizations of 2-DORGs such as a one based on forbidden submatrices, a one in terms of a vertex ordering, a one by circular arc graphs, and a one by forbidden induced subgraphs. The characterizations imply a polynomial time recognition algorithm for 2-DORGs. We introduce some intersection bigraphs related to ORGs, and review relationships between them. We finally review the complexities of various combinatorial problems for ORGs and related graphs. The characterization of ORGs and 3- DORGs still remains open.
2013-10-30

[招待講演]Orthogonal Ray Graphs with Applications to Nanocircuit Design

スポンサーリンク

概要

著者

関連論文

スポンサーリンク