  We present a new Dynamic Programming (DP) formulation of the Coalition
Structure Generation (CSG) problem based on imposing a hierarchical
organizational structure over the agents. We show the efficiency of this
formulation by deriving DyPE, a new optimal DP algorithm which significantly
outperforms current DP approaches in speed and memory usage. In the classic
case, in which all coalitions are feasible, DyPE has half the memory
requirements of other DP approaches. On graph-restricted CSG, in which
feasibility is restricted by a (synergy) graph, DyPE has either the same or
lower computational complexity depending on the underlying graph structure of
the problem. Our empirical evaluation shows that DyPE outperforms the
state-of-the-art DP approaches by several orders of magnitude in a large range
of graph structures (e.g. for certain scalefree graphs DyPE reduces the memory
requirements by $10^6$ and solves problems that previously needed hours in
minutes).
