| Presentation | 2015-06-13 On a Self-Stabilizing Algorithm for constructing a (1, 1)-Maximal Directed Acyclic Graph Using st-ordering Haruka Ono, Yoshiaki Katayama, Toshimitsu Masuzawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose a new network structure (s, t)-Maximal DAG and a self-stabilizing algorithm for constructing (1, 1)-Maximal DAG on any undirected connected graph. An (s, t)-Maximal DAG is a graph consistingof directed and undirected edges with given S sources and T sinks, which has no directed cycle (consisting only of directed edges) but creates a directed cycle by directing any edge in any direction. The proposed algorithm is obtained by fair composition of 2 known and 3 new algorithms composed by fair composition. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | self-stabilization / DAG / (s, t)-Maximal DAG / DFS tree / articulation point |
| Paper # | COMP2015-12 |
| Date of Issue | 2015-06-05 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2015/6/12(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Koichi Wada(Hosei Univ.) |
| Vice Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Secretary | Toshimitsu Masuzawa(Hiroshima Univ.) / (Univ. of Electro-Comm.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On a Self-Stabilizing Algorithm for constructing a (1, 1)-Maximal Directed Acyclic Graph Using st-ordering |
| Sub Title (in English) | |
| Keyword(1) | self-stabilization |
| Keyword(2) | DAG |
| Keyword(3) | (s, t)-Maximal DAG |
| Keyword(4) | DFS tree |
| Keyword(5) | articulation point |
| 1st Author's Name | Haruka Ono |
| 1st Author's Affiliation | Nagoya Institute of Technology(NIT) |
| 2nd Author's Name | Yoshiaki Katayama |
| 2nd Author's Affiliation | Nagoya Institute of Technology(NIT) |
| 3rd Author's Name | Toshimitsu Masuzawa |
| 3rd Author's Affiliation | Osaka University(OU) |
| Date | 2015-06-13 |
| Paper # | COMP2015-12 |
| Volume (vol) | vol.115 |
| Number (no) | COMP-84 |
| Page | pp.pp.115-122(COMP), |
| #Pages | 8 |
| Date of Issue | 2015-06-05 (COMP) |