The rook problem on saw-toothed chessboards

NCUTIR > College of Management > Department of Information Management > 【資訊管理系】期刊論文 > Item 987654321/3364

Please use this identifier to cite or link to this item: http://ir.lib.ncut.edu.tw/handle/987654321/3364

Title:	The rook problem on saw-toothed chessboards
Authors:	Hon-Chan Chen;Ting-Yem Ho
Contributors:	勤益科技大學
Date:	2008-12
Issue Date:	2010-03-22 18:12:36 (UTC+8)
Abstract:	A saw-toothed chessboard, or STC for short, is a kind of chessboard whose boundary forms two staircases from left down to right without any hole inside it. A rook at square (i,j) can dominate the squares in row i and in column j. The rook problem of an STC is to determine the minimum number of rooks that can dominate all squares of the STC. In this paper, we model an STC by two particular graphs: a rook graph and a board graph. We show that for an STC, the rook graph is the line graph of the board graph, and the board graph is a bipartite permutation graph. Thus, the rook problem on STCs can be solved by any algorithm for solving the edge domination problem on bipartite permutation graphs.
Relation:	Applied Mathematics Letters
Appears in Collections:	[Department of Information Management] 【資訊管理系】期刊論文

Files in This Item:

File	Description	Size	Format
The rook problem on saw-toothed chessboards.pdf		290Kb	Adobe PDF	2446	View/Open