The automatic synthesis of movements for legged robots is one of the long standing challenge of robotics, and its resolution is a prior to the safe deployment of robots outside of their labs. In this thesis, we tackle it with a divide and conquer approach, where several smaller sub-problems are identified and solved sequentially to generate motions in a computationally efficient manner. This decoupling comes with a feasibility issue : how can we guarantee that the solution of a sub-problem is a valid input for the next sub-problem ? To address this issue, this thesis defines computationally efficient feasibility criteria, focused on the constraints on the Center Of Mass of the robot. Simultaneously, it proposes a new formulation of the problem of computing a feasible trajectory for the Center Of Mass of the robot, given a contact sequence. This formulation is continuous, as opposed to traditional approaches that rely on a discretized formulation, which can result in constraint violations and are less computationally efficient. This general formulation could be straightforwardly used with any existing approach of the state of the art. The framework obtained was experimentally validated both in simulation and on the HRP-2 robot, and presented a higher success rate, as well as computing performances order of magnitudes faster than the state of the art.