We present an algorithm that given a graph computes a subgraph of maximum ‘density’. (For unweighed graphs, density is the edges-to-vertices ratio). The proposed algorithm is asymptotically more efficient than the currently available ones. Our approach remains efficient for weighed graphs and more generally for weighed set-systems. Two faster approximation algorithms are offered, and a number of applications are discussed.

We view the 'packet-switching problem' (from N inputs towards N outputs) from the perspective of game theory and we prove that, if the rates of flows are weighed then 'weighed max-min fair service rates' are the unique Nash equilibrium point of a natural strategic game in which throughput is granted on a 'least-demanding first-served' principle. We prove that a crossbar switching device with suitably randomized schedulers converges to this equilibrium point without pre-computing it.

We generalize the technique of classic splay trees of Sleator and Tarjan, showing that almost all template-based rules for self-adjusting a multi-way tree have logarithmic amortized cost and other properties of splay trees, such as ‘static optimality’, the ‘static finger’ and ‘working set’ properties. We achieve this by defining in a new way (through ‘progress factors’) a potential on a weighted tree, and by introducing a new technique (which we call ‘± calculus’) for calculating the changes in potential.

‘Unit execution time’ precedence constrained scheduling (UET) is an NP-complete problem with very few special cases known to be solvable in P-time. In this article we present a practically useful case of UET solvable in P-time: we show that if the task graph is given in levels that are ‘locally’ of in-degree two and of ‘width’ more than 1.55 times the number of processors (plus 1), then an optimal schedule can be found in P-time. Task graphs which represent algebraic computations fall ordinarily in this category. Our algorithm is based on a limited look-ahead technique which allows us to use it in an on-line fashion. In the appendix we give two short NP-completeness proofs which suggest that both ‘width’ and ‘degree’ restrictions are needed to get a polynomially solvable subcase.