| 大会名称 |
| 2016年 ソサイエティ大会 |
| 大会コ－ド |
| 2016S |
| 開催年 |
|
2016
|
| 発行日 |
|
2016-09-06
|
| セッション番号 |
|
A-1
|
| セッション名 |
|
回路とシステム
|
| 講演日 |
|
2016/9/20
|
| 講演場所(会議室等) |
|
工学部 N棟 N307
|
| 講演番号 |
|
A-1-10
|
| タイトル |
|
A Note on the Parallel Complexity of Doubly Lexical Orderings
|
| 著者名 |
|
◎Tsukasa Kobayashi, Satoshi Tayu, Shuichi Ueno,
|
| キーワード |
|
doubly lexical ordering, chain graph, tree
|
| 抄録 |
|
For a 0-1 matrix, an ordering of the rows and columns is called a doubly lexical ordering if the row vectors are lexically increasing and the column vectors are lexically increasing. A bigraph G with a bipartition (X,Y) is called a chain bigraph if the vertices of G can be ordered so that the neighbors of xi includes the neighbors of xj and the neighbors of yi includes the neighbors of yj if i ＞ j. The purpose of the note is to show NC algorithms to compute doubly lexical orderings for trees and chain graphs, simple subclasses of bigraphs.
|
| 本文pdf |
|
PDF download
|
