Frontier dynamic programming Created 2026-10-20 Updated 2026-11-05
Frontier dynamic programming processes a graph or grid in an order and remembers only the processed vertices that still meet unprocessed edges, together with the information needed across that frontier. Its complexity is controlled by frontier width rather than merely by the total vertex count.
For counting paths on a strip, the state may need both vertex degrees and which frontier endpoints are connected through the processed region. Two configurations with the same occupied frontier vertices can differ in whether the next edge closes a forbidden cycle. Recording a canonical connectivity partition prevents this loss of information. This is a graph-oriented form of state compression and transfer dynamic programming.
State compression Created 2026-10-20 Updated 2026-11-05
State compression replaces a dynamic programming history by a smaller summary that retains everything needed to determine future legal choices, costs and transitions. Histories may be merged only when their summaries make all relevant continuations equivalent.
For selecting a subset of objects, an -bit mask stores membership in one integer. A path problem may additionally need the final vertex: two partial paths visiting the same subset can have different continuation costs if their endpoints differ. Compression saves storage by discarding irrelevant history; omitting relevant state changes the problem rather than optimizing its solution.