With regards to the retrospective or off-line multiple change-point detection problem, much effort has been devoted in recent years to the selection of the optimal number of change points. Here, we explore another research direction which focuses on exploring the space of possible segmentations for successive numbers of change points. The knowledge of solely the most probable segmentation of a sequence (for a fixed number of change points) tells us nothing about the remainder of the segmentation space. Questions of interest are: o Is the most probable segmentation most probable by a long way or are there other segmentations with near-optimal probability? o Are these near-optimal segmentations very similar to the most probable segmentation or do they differ greatly? Methods for exploring the space of possible segmentations may be divided into two categories: (i) enumeration of possible segmentations, (ii) change-point or segment profiles i.e. possible segmentations summarized in a J × T array where J is the number of segments (hence, the number of change points is J ? 1) and T the length of the sequence. Various dynamic programming and smoothing-type algorithms belonging to these two categories are presented. The dynamic programming algorithms rely on additive contrast functions (e.g. sum of squared deviations from the mean in the Gaussian case) while the smoothing-type algorithms rely on additive log-likelihood functions. Hence, the smoothing-type algorithms apply to a more restricted class of change-point models than the dynamic programming algorithms. Models of this class are characterized by a separability property, i.e. there is no global parameter that depends on within-segment parameters. Due to the deterministic succession of segments, most of the proposed algorithms have transdimensional properties, that is, the output of an algorithm for K segments, with K = 2, . . . , J ? 1, can be computed as an almost free byproduct of the application of this algorithm f