Solving the minimum dominating set problem with instance-specific hardware on FPGAs

Author

Wakabayashi, Shin´ichi ; Kikuchi, Kenji

Author_Institution

Fac. of Inf. Sci., Hiroshima City Univ.

fYear

2005

fDate

11-14 Dec. 2005

Firstpage

69

Lastpage

76

Abstract

This paper presents an instance specific hardware algorithm for finding a minimum dominating set of a given graph. The proposed algorithm is constructed according to a given instance of graph, and can find a minimum dominating set efficiently based on branch and bound search. Experimental results showed that, compared with the software solver, the proposed algorithm implemented on FPGAs produced a minimum dominating set in a much shorter running time even if the time for circuit synthesis and configuration of FPGA was taken into account

Keywords

field programmable gate arrays; graph theory; tree searching; FPGA configuration; branch and bound search; circuit synthesis; field programmable gate array; instance specific hardware algorithm; minimum dominating set problem; Application software; Circuit synthesis; Computer networks; Field programmable gate arrays; Hardware design languages; NP-hard problem; Parallel processing; Pipelines; Problem-solving; Software algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Field-Programmable Technology, 2005. Proceedings. 2005 IEEE International Conference on

Conference_Location

Singapore

Print_ISBN

0-7803-9407-0

Type

conf

DOI

10.1109/FPT.2005.1568527

Filename

1568527