Relation-algebraic modeling and solution of chessboard independence and domination problems. (English) Zbl 1280.68301
Summary: We describe a simple computing technique for solving independence and domination problems on rectangular chessboards. It rests upon relational modeling and uses the BDD-based specific purpose computer algebra system RelView for the evaluation of the relation-algebraic expressions that specify the problems’ solutions and the visualization of the computed results. The technique described in the paper is very flexible and especially appropriate for experimentation. It can easily be applied to other chessboard problems.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 68R05 | Combinatorics in computer science |
| 91A46 | Combinatorial games |
Keywords:
relation algebra; relational modeling; chessboard relation; independence; domination; Bishops independence numberSoftware:
RelViewReferences:
| [1] | Bell, J.; Stevens, B., A survey of known results and research areas for \(n\) queens, Discrete Math., 309, 1-31 (2008) · Zbl 1228.05002 |
| [2] | Berghammer, R., Applying relation algebra and RelView to solve problems on orders and lattices, Acta Inform., 45, 211-236 (2008) · Zbl 1144.68053 |
| [3] | Berghammer, R.; Neumann, F., RelView - an OBDD-based computer algebra system for relations, (Gansha, V. G.; Mayr, E. W.; Vorozhtsov, E., Computer Algebra in Scientific Computing. Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, vol. 3718 (2006), Springer), 40-51 · Zbl 1144.68384 |
| [4] | R. Berghammer, G. Schmidt, The RelView; R. Berghammer, G. Schmidt, The RelView |
| [5] | Berghammer, R.; Rusinowska, A.; de Swart, H., An interdisciplinary approach to coalition formation, Eur. J. Oper. Res., 195, 487-496 (2009) · Zbl 1159.91311 |
| [6] | Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and RelView to measures in a social network, Eur. J. Oper. Res., 202, 182-198 (2010) · Zbl 1173.91446 |
| [7] | Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., C-35, 8, 677-691 (1986) · Zbl 0593.94022 |
| [8] | Bryant, R. E., Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surv., 24, 293-318 (1992) |
| [9] | Burch, J. R.; Clarke, E. M.; McMillan, K. L.; Dill, DE. I.; Hwang, L. I., Symbolic model checking: \(10^{20}\) states and beyond, (Proc. Fifth Annual Symphosium on Logic in Computer Science (1990), IEEE Computer Science), 428-439 |
| [10] | Chen, H.-C.; Ho, T.-Y., The rook problem on saw-toothed chessboards, Appl. Math. Lett., 21, 1234-1237 (2008) · Zbl 1229.90153 |
| [11] | Cockayne, E. J., Chessboard domination problems, Discrete Math., 86, 13-20 (1990) · Zbl 0818.05057 |
| [12] | de Jaenisch, C. F., Applications de l’analyse mathematiques au jeu des echecs (1882), Petrograd |
| [13] | Desharnais, J., Monomorphic characterization of \(n\)-ary direct products, Inform. Sci., 119, 275-288 (1999) · Zbl 0942.03041 |
| [14] | (Embley, D.; Thalheim, B., Handbook of Conceptual Modeling Theory (2011), Springer) · Zbl 1213.68001 |
| [15] | Gibbons, P. B.; Webb, J. A., Some new results for the queens domination problem, Austral. J. Combin., 15, 145-160 (1997) · Zbl 0880.05023 |
| [16] | http://www.informatik.uni-kiel.de/∼;relview.shtml; http://www.informatik.uni-kiel.de/∼;relview.shtml |
| [17] | http://queens.inf.tu-dresden.de; http://queens.inf.tu-dresden.de |
| [18] | http://www-ps.informatik.uni-kiel.de/currywiki; http://www-ps.informatik.uni-kiel.de/currywiki |
| [19] | B. Leoniuk, ROBDD-basierte Implementierung von Relationen und relationalen Operationen mit Anwendungen, Dissertation, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, 2001.; B. Leoniuk, ROBDD-basierte Implementierung von Relationen und relationalen Operationen mit Anwendungen, Dissertation, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, 2001. |
| [20] | U. Milanese, Zur Implementierung eines ROBDD-basierten Systems für die Manipulation und Visualisierung von Relationen. Dissertation, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, 2003.; U. Milanese, Zur Implementierung eines ROBDD-basierten Systems für die Manipulation und Visualisierung von Relationen. Dissertation, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, 2003. |
| [21] | Nauck, F., Briefwechsel mit allen für alle, Illustrirte Zeitung, 15, 182 (1850) |
| [22] | Pauls, E., Das Maximalproblem der Damen auf dem Schachbrett, Deutsche Schachzeitung, 29, 129-134 (1874) |
| [23] | Schmidt, G., Relational mathematics, Encyclopedia of Mathematics and its Applications, vol. 132 (2010), Cambridge University Press |
| [24] | Schmidt, G.; Ströhlein, T., Relations and Graphs, Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoretical Computer Science (1993), Springer · Zbl 0900.68328 |
| [25] | Steinbach, B.; Posthoff, C., New results based on Boolean models, (Steinbach, B., Proc. 9th International Workshop on Boolean Problems (2010), TU Bergakademie Freiberg), 29-36 |
| [26] | Watkins, J. J., Across the Board: The Mathematics of Chessboard Problems (2004), Princeton University Press · Zbl 1108.00007 |
| [27] | Wegener, I., Branching Programs and Binary Decision Diagrams, Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications (2000), SIAM · Zbl 0956.68068 |
| [28] | Yaglom, A. M.; Yaglom, I. M., Challenging Mathematical Problems with Elementary Solutions, Combinatorial Analysis and Probability Theory, vol. I (1964), Holden-Day Inc. · Zbl 0123.24201 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
