A simple method is presented for ensuring that at least half the possible alignments of logic trees in a rail will be achieved. Given t logic trees over n variables, the problem is twofold: place the trees in a sequential order (in a rail) while simultaneously using switching to position variables in the trees to achieve maximal alignment. (A logic tree is an n × 2 matrix over the input variables, with possibly empty entries.) Alignment occurs when entries of adjacent columns of identical levels coincide.

Achieving the maximum number of alignments is NP-complete, but the author’s heuristic is guaranteed to produce at least half the maximum. Given an alignment graph G of the trees, the heuristic, based on the match-and-combine principle of Sarrafzadeh and Preparata [1], computes a maximum-weighted matching in G. The matched nodes are combined and a new alignment graph is constructed. The matching is repeated until only one node remains. The initial matching provably gives at least half the maximum number of matches, so the follow-up heuristic algorithm often produces good results. Further, by an elegant reduction of two-tree matching to maximum matching in permutation graphs, the matching is achieved in O ( t ³ + t ² c n ² log n ) time, where c is the maximum number of configurations of a tree.