| No | 193837 |
|---|---|
| 標題（和） | ［ポスター講演］A Note on Two Problems of Nano-PLA Design |
| 標題（英） | [Poster Presentation] A Note on Two Problems of Nano-PLA Design |
| 研究会名（和） | 回路とシステム, 通信方式, 信号処理 |
| 研究会名（英） | Circuits and Systems, Communication Systems, Signal Processing |
| 開催年月日 | 2009-03-02 |
| 終了年月日 | 2009-03-03 |
| 会議種別コード | 5 |
| 共催団体名（和） | |
| 資料番号 | CAS2008-133, SIP2008-196, CS2008-107 |
| 抄録（和） | |
| 抄録（英） | This paper shows that the subgraph isomorphism problem is NP-hard even for bipartite permutation graphs, while the balanced complete bipartite subgraph problem can be solved in O(n + m) time for a bipartite permutation graph with n vertices and m edges. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.108, No.453,454,455 |
| ページ開始 | 183 |
| ページ終了 | 184 |
| キーワード（和） | |
| キーワード（英） | balanced complete bipartite subgraph,bipartite permutation graph,chordal bipartite graph,nano–PLA,NP-hard,orthogonal ray graph,polynomial-time algorithm,subgraph isomorphism |
| 本文の言語 | ENG |
| 著者（和） | Anish Man Singh Shrestha |
| 著者（ヨミ） | |
| 著者（英） | Anish Man Singh Shrestha |
| 所属機関（和） | Tokyo Institute of Technology |
| 所属機関（英） | Tokyo Institute of Technology |
| 著者（和） | 山田朋輝 |
| 著者（ヨミ） | |
| 著者（英） | Tomoki Yamada |
| 所属機関（和） | Tokyo Institute of Technology |
| 所属機関（英） | Tokyo Institute of Technology |
| 著者（和） | 田湯智 |
| 著者（ヨミ） | |
| 著者（英） | Satoshi Tayu |
| 所属機関（和） | Tokyo Institute of Technology |
| 所属機関（英） | Tokyo Institute of Technology |
| 著者（和） | 上野修一 |
| 著者（ヨミ） | |
| 著者（英） | Shuichi Ueno |
| 所属機関（和） | Tokyo Institute of Technology |
| 所属機関（英） | Tokyo Institute of Technology |