| Paper Abstract and Keywords |
| Presentation |
2005-11-10 16:15
A Branch and Bound Algorithm for the Minimum Dominating Set Problem and its Hardware Implementation on FPGAs
Kenji Kikuchi, Shin'ichi Wakabayashi (Hiroshima City Univ.) |
| Abstract |
(in Japanese) |
(See Japanese page) |
| (in English) |
A branch and bound algorithm for finding a minimum dominating set of a given graph was proposed,and experimental evaluation of the proposed algorithm was presented. The proposed algorithm was also realized as a hardware circuit, which was constructed according to a given instance of graph, and can find a minimum dominating set efficiently. The proposed hardware algorithm was implemented on an FPGA, and its running time was measured. Compared with an ordinary software implementation of the algorithm, the proposed algorithm found a minimum dominating set in a shorter running time. |
| Keyword |
(in Japanese) |
(See Japanese page) |
| (in English) |
minimum dominating set / branch and bound / FPGA / instance-specific / / / / |
| Reference Info. |
IEICE Tech. Rep., vol. 105, no. 387, CAS2005-59, pp. 57-62, Nov. 2005. |
| Paper # |
CAS2005-59 |
| Date of Issue |
2005-11-03 (CAS, CST) |
| ISSN |
Print edition: ISSN 0913-5685 |
| Download PDF |
|
| Conference Information |
| Committee |
MSS CAS |
| Conference Date |
2005-11-10 - 2005-11-11 |
| Place (in Japanese) |
(See Japanese page) |
| Place (in English) |
Yamaguchi University |
| Topics (in Japanese) |
(See Japanese page) |
| Topics (in English) |
Graph theory, Petri net, Neural network, etc. |
| Paper Information |
| Registration To |
CAS |
| Conference Code |
2005-11-CST-CAS |
| Language |
Japanese |
| Title (in Japanese) |
(See Japanese page) |
| Sub Title (in Japanese) |
(See Japanese page) |
| Title (in English) |
A Branch and Bound Algorithm for the Minimum Dominating Set Problem and its Hardware Implementation on FPGAs |
| Sub Title (in English) |
|
| Keyword(1) |
minimum dominating set |
| Keyword(2) |
branch and bound |
| Keyword(3) |
FPGA |
| Keyword(4) |
instance-specific |
| Keyword(5) |
|
| Keyword(6) |
|
| Keyword(7) |
|
| Keyword(8) |
|
| 1st Author's Name |
Kenji Kikuchi |
| 1st Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
| 2nd Author's Name |
Shin'ichi Wakabayashi |
| 2nd Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
| 3rd Author's Name |
|
| 3rd Author's Affiliation |
() |
| 4th Author's Name |
|
| 4th Author's Affiliation |
() |
| 5th Author's Name |
|
| 5th Author's Affiliation |
() |
| 6th Author's Name |
|
| 6th Author's Affiliation |
() |
| 7th Author's Name |
|
| 7th Author's Affiliation |
() |
| 8th Author's Name |
|
| 8th Author's Affiliation |
() |
| 9th Author's Name |
|
| 9th Author's Affiliation |
() |
| 10th Author's Name |
|
| 10th Author's Affiliation |
() |
| 11th Author's Name |
|
| 11th Author's Affiliation |
() |
| 12th Author's Name |
|
| 12th Author's Affiliation |
() |
| 13th Author's Name |
|
| 13th Author's Affiliation |
() |
| 14th Author's Name |
|
| 14th Author's Affiliation |
() |
| 15th Author's Name |
|
| 15th Author's Affiliation |
() |
| 16th Author's Name |
|
| 16th Author's Affiliation |
() |
| 17th Author's Name |
|
| 17th Author's Affiliation |
() |
| 18th Author's Name |
|
| 18th Author's Affiliation |
() |
| 19th Author's Name |
|
| 19th Author's Affiliation |
() |
| 20th Author's Name |
|
| 20th Author's Affiliation |
() |
| Speaker |
Author-1 |
| Date Time |
2005-11-10 16:15:00 |
| Presentation Time |
25 minutes |
| Registration for |
CAS |
| Paper # |
CAS2005-59, CST2005-28 |
| Volume (vol) |
vol.105 |
| Number (no) |
no.387(CAS), no.389(CST) |
| Page |
pp.57-62 |
| #Pages |
6 |
| Date of Issue |
2005-11-03 (CAS, CST) |
|