| 大会名称 |
| 2016年 ソサイエティ大会 |
| 大会コ－ド |
| 2016S |
| 開催年 |
|
2016
|
| 発行日 |
|
2016-09-06
|
| セッション番号 |
|
A-1
|
| セッション名 |
|
回路とシステム
|
| 講演日 |
|
2016/9/20
|
| 講演場所(会議室等) |
|
工学部 N棟 N307
|
| 講演番号 |
|
A-1-11
|
| タイトル |
|
A Parallel Matching Algorithm for Chain Graphs
|
| 著者名 |
|
○Ryu Sugimoto, Satoshi Tayu, Shuichi Ueno,
|
| キーワード |
|
maximum matching, chain bigraph, parallel algorithm
|
| 抄録 |
|
A bigraph with a bipartition (X, Y) is called a chain bigraph if the vertices of X can be ordered so that N(x1) ⊆ N(x2) ⊆ ... ⊆ N(xp), where X = {x1, x2, ... , xp}, and N(v) is the set of vertices adjacent with a vertex i. A set M of edge of a graph is called a matching if no two edges in M have a common endvertex. An NC algorithm is a parallel algorithm running in a polylogarithmic time using a polynomial number of processors. This paper shows an NC algorithm to obtain a maximum matching of a chain bigraph.
|
| 本文pdf |
|
PDF download
|
