In this paper we consider three fundamental communication problems on the star interconnection network: the problem of simultaneous broadcasting of a message from every node to all other nodes, or multinode broadcasting, the problem of a single node sending distinct messages to each one of the other nodes, or single-node scattering, and finally the problem of each node sending distinct messages to every other node, or total exchange. All of these problems are studied under two different assumptions: the assumption that each node can transmit a message of fixed length to one of its neighbors and simultaneously receive a message of fixed length from one of its neighbors (not necessarily the same one) at each time step, or single-link availability, and the assumption that each node can exchange messages of fixed length with all of its neighbors at each time step, or multiple-link availability. In both cases communication is assumed to be bidirectional. The cases where the originating processor wishes to send only one or more than one message to each one of the other processors are distinguished when necessary. Lower bounds are derived for these problems under the stated assumptions, and optimal algorithms are designed in terms of both time and number of message transmissions. Although the algorithms derived for the first two problems require the minimum amount of the above resources, the algorithm designed for the total exchange problem is optimal only to within a multiplicative factor. All the communication algorithms presented in this paper are based on the construction of spanning trees with special properties on the star graph to fit different communication needs. A special framework is developed to facilitate the construction of these trees. The scheduling disciplines that lead to optimal results in each case are described.