A divide-and-conquer algorithm for generating Markov bases of multi-way tables (Q1775965)

The paper focuses on sets of \(k\)-way tables of counts that are induced by fixing several lower dimensional marginals. The authors demonstrate how using the graphical structure of the mentioned class of tables can significantly reduce the amount of computations necessary for generating a Markov basic. They describe a relevant ``divide-and-conquer'' procedure based on decomposition of the independence graph induced by fixed marginals, study properties of decomposable and reducible graphs and propose a divide-and-conquer algorithm. They also discuss the practical importance of using such method in conjunction with other algorithms for generating Markov bases.