The paper discusses two methods for optimal program linearization from the viewpoint of minimizing the number of unconditional jumps. The first one relates to the simple case when only unconditional jumps are considered. This task can be formulated as the task of finding optimal path covering for a subgraph of CFG (Control Flow Graph). The subgraph in question (Fall Through Graph — FTG) includes only fallthrough edges and the vertices connected with them. The method implies finding the optimal "path and cycle" covering of FTG with subsequent breaking of cycles. The complexity of the algorithm is O(N) where N is the number of vertices in FTG.

The final section of the paper discusses the NP-complete task of path covering of an arbitrary digraph which arises during optimal program linearization with respect to all kinds of jumps including conditional ones. We propose a recursive enumeration based on building the optimal "path and cycle" covering of the digraph with subsequent breaking of cycles.