Chessboard domination on programmable graphics hardware

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Chessboard domination on programmable graphics hardware

Full text

Pdf (208 KB)

Source

ACM Southeast Regional Conference archive
Proceedings of the 44th annual Southeast regional conference table of contents

Melbourne, Florida

SESSION: Graphics and real-time systems table of contents

Pages: 62 - 67

Year of Publication: 2006

ISBN:1-59593-315-8

Author

Nathan Cournia

Clemson University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1185448.1185463 What is a DOI?

ABSTRACT

In this paper we present an algorithm to compute the minimum dominating number of a chessboard graph given any chess piece. We use the CPU to compute possible minimally dominating sets, which we then send to programmable graphics hardware to determine the set's domination. We find that the GPU accelerated algorithm performs better than a comparable CPU based algorithm for board sizes greater than 9. To our knowledge, this paper presents the first algorithm to determine the minimum domination number of a chessboard graph using the GPU.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	2	A. P. Burger , C. M. Mynhardt, An upper bound for the minimum number of queens covering the n × n chessboard, Discrete Applied Mathematics, v.121 n.1-3, p.51-60, 15 September 2002 [doi>10.1016/S0166-218X(01)00244-X]
	3	Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
	4	A. P. Burger, E. J. Cockayne, and C. M. Mynhardt. Domination numbers for the queen's graph. Bull. Inst. Combin. Appl., 10:73--82, 1994.
	5	A. P. Burger , E. J. Cockayne , C. M. Mynhardt, Domination and irredundance in the queens' graph, Discrete Mathematics, v.163 n.1-3, p.47-66, Jan. 15, 1997 [doi>10.1016/0012-365X(95)00327-S]
	6	A. P. Burger and C. M. Mynhardt. Properties of dominating sets of the queens graph Q4k+3.Utilitas Math., 57:237-253, 2000.
	7	A. P. Burger and C. M. Mynhardt. Symmetry and domination in queens graphs. Bull. Inst. Combin. Appl., 29:11--14, 2000.
	8	A. P. Burger , C. M. Mynhardt, An improved upper bound for queens domination numbers, Discrete Mathematics, v.266 n.1-3, p.119-131, 6 May 2003 [doi>10.1016/S0012-365X(02)00802-6]
	9	E. J. Cockayne, Chessboard domination problems, Discrete Mathematics, v.86 n.1-3, p.13-20, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90344-H]
	10	C. F. A. de Jaenisch. Traité des Applications de l'Analyse Mathématique au Jeu des Échecs. St. Pétersbourg, 1862.
	11	P. B. Gibbons and J. A. Webb. Some new results for the queens domination problem. Australas. J. Combin., 15:145--160, 1997.
	12	Mark J. Harris , William V. Baxter , Thorsten Scheuermann , Anselmo Lastra, Simulation of cloud dynamics on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
	13	T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Funamentals of Domination in Graphs. Marcel-Dekker, New York, 1998.
	14	S. T. Hedetniemi and R. C. Laskar. Introduction. Discrete Math., 86:3--9, 1990.
	15	M. D. Kearse and P. B. Gibbons. Computational methods and new results for chessboard problems. Australas. J. Combin., 23:253--284, 2001.
	16	Brucek Khailany , William J. Dally , Scott Rixner , Ujval J. Kapasi , John D. Owens , Brian Towles, Exploring the VLSI Scalability of Stream Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.153, February 08-12, 2003
	17	Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	18	P. R. J. Östergård and W. D. Weakley. Values of domination numbers of the queen's graph. The Electronic Journal of Combinatorics, 8(1), 2001.
	19	Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	20	Semiconductor Industry Association. International technology roadmap for semiconductors. http://public.itrs.net/, December 2002.
	21	Robert Wagner , Robert Geist, The crippled queen placement problem, Science of Computer Programming, v.4 n.3, p.221-248, Dec. 1984 [doi>10.1016/0167-6423(84)90001-7]
	22	W. D. Weakley. Domination in the queen's graph. In Y. Alavi and A. J. Schwenk, editors, Graph Theory, Combinatorics, and Algorithms, volume 2, pages 1223--1232, New York, 1995. Wiley-Interscience.
	23	W. D. Weakley. A lower bound for domination numbers of the queen's graph. The Electronic Journal of Combinatorics, 8(1), 2001.
	24	William D. Weakley, Upper bounds for domination numbers of the queen's graph, Discrete Mathematics, v.242 n.1-3, p.229-243, January 06, 2002 [doi>10.1016/S0012-365X(00)00467-2]