Sequentially rejective pairwise testing procedures (Q1108720)

\textit{S. Holm}'s sequentially rejective procedure [Scand. J. Stat., Theory Appl. 6, 65-70 (1979; Zbl 0402.62058)] was developed for families of hypotheses which allow `free combinations'. Two modifications of Holm's procedure for the family of pairwise hypotheses were discussed by \textit{P. J. Shaffer} [see J. Am. Stat. Assoc. 81, 826-831 (1986; Zbl 0603.62087)]. However, the more powerful modification is only illustrated for the case \(k=4\) means and not discussed further because of the prohibitive computational effort it requires even when k is moderate. We first note that Shaffer's powerful sequentially rejective procedure is equivalent to \textit{E. Peritz}'s [A note on multiple comparisons. Unpublished paper. Hebrew Univ. (1970)] closed testing scheme when a natural relation holds between the corresponding critical values. This raises the question of whether conditions exist under which a computationally efficient algorithm can be derived for implementing that procedure. We identified conditions under which a very efficient algorithm is given. The given conditions are quite restrictive but extremely simple to test in each particular case. In developing the algorithm we use a graph theory approach and provide some new results which are potentially of independent theoretical interest.