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.

Articles by others on the same topic (0)

There are currently no matching articles.