| Presentation | 2013-01-23 Proposal of Algorithm to Finding Determiner Set for Graphs Kurumi KOUCHI, Mitsuru NAKATA, Qi-Wei GE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Given with a graph G and its isomorphic graph G', there may have multiple one-to-one correspondences between the vertices of G and G'. If a part of correspondences of vertices are assigned then the correspondences of the remaining vertices can be uniquely determined. Such a set of assigned vertices is called determiner set and a determiner set is called minimum determiner set if no any its proper subset is determiner set. Further, a minimum determiner set with the least number of elements is called kernel set. In this paper, first we give necessary definitions and properties of determiner set as well as minimum determiner set and kernel set. Next we propose graph operations and an algorithm to find a determiner set and further propose an algorithm to find a minimum determiner set. Finally, we apply these algorithms to rescue workers' positioning problem to show the usefulness of our algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph / isomorphic graph / kernel set / determiner set / minimum determiner set |
| Paper # | MSS2012-57 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2013/1/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Proposal of Algorithm to Finding Determiner Set for Graphs |
| Sub Title (in English) | |
| Keyword(1) | graph |
| Keyword(2) | isomorphic graph |
| Keyword(3) | kernel set |
| Keyword(4) | determiner set |
| Keyword(5) | minimum determiner set |
| 1st Author's Name | Kurumi KOUCHI |
| 1st Author's Affiliation | Faculty of Education, Yamaguchi University() |
| 2nd Author's Name | Mitsuru NAKATA |
| 2nd Author's Affiliation | Faculty of Education, Yamaguchi University |
| 3rd Author's Name | Qi-Wei GE |
| 3rd Author's Affiliation | Faculty of Education, Yamaguchi University |
| Date | 2013-01-23 |
| Paper # | MSS2012-57 |
| Volume (vol) | vol.112 |
| Number (no) | 383 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |