Call a bipartite graph G = (X, Y ; E) balanced when |X| = |Y |. Given a balanced bipartite graph G with edge costs, the assignment problem asks for a perfect matching in G of minimum total cost. The Hungarian Method can solve assignment problems in time O(mn+n2log n), where n := |X| = |Y | and m := |E|. If the edge weights are integers bounded in magnitude by C >; 1, then algorithms using weight scaling, such as that of Gabow and Tarjan, can lower the time to O(m√n log(nC)). There are important applications in which G is unbalanced, with |X| ≠ |Y |, and we require a min-cost matching of size r := min(|X|, |Y |) or, more generally, of some specified size s ≤ r. The Hungarian Method extends easily to find such a matching in time O(ms + s2log r), but weightscaling algorithms do not extend so easily. We introduce new machinery to find such a matching in time O(m√s log(sC)) via weight scaling. Our results provide some insight into the design space of efficient weight-scaling matching algorithms.

Suppose we want to eliminate the local go to statements of a Pascal program by replacing them with multilevel loop exit statements. The standard ground rules for eliminating go to's require that we preserve the flow graph of the program, but they allow us to completely rewrite the control structures that glue together the program's atomic tests and actions. The go to's can be eliminated from a program under those ground rules if and only if the flow graph of that program has the graph-theoretic property named reducibility. This paper considers a stricter set of ground rules, introduced by Peterson, Kasami, and Tokura, which demand that we preserve the program's original control structures, as well as its flow graph, while we eliminate its go to's. In particular, we are allowed to delete the go to statements and the labels that they jump to and to insert various exit statements and labeled repeat-endloop pairs for them to jump out of. But we are forbidden to change the rest of the program text in any way. The critical issue that determines whether go to's can be eliminated under these stricter rules turns out to be the static order of the atomic tests and actions in the program text. This static order can be encoded in the program's flow graph by augmenting it with extra edges. It can then be shown that the reducibility of a program's augmented flow graph, augmenting edges and all, is a necessary and sufficient condition for the eliminability of go to's from that program under the stricter rules.

Delange has demonstrated an elegant method for computing the sum of all of the digits used when the first n nonnegative integers are expressed in base $q \geqq 2$. We show that his method can be adapted to unusual number systems such as Gray code and balanced ternary and can also be adapted to count the occurrences of each digit separately. As an application, we consider Sedgewick’s analysis of Batcher’s odd-even merge, and use our results about Gray code to provide an alternative, and perhaps more direct,derivation of the asymptotics of the average case.