کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1709145 1012843 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The rook problem on saw-toothed chessboards
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
The rook problem on saw-toothed chessboards
چکیده انگلیسی

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)(i,j) can dominate the squares in row ii and in column jj. 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 21, Issue 12, December 2008, Pages 1234–1237
نویسندگان
, ,