Algebraic Expressions for Directed Grid Graphs with Diagonal Edges: Decomposition Bounds, Lower Bounds, and Algebraic-Branching-Program Methods
This paper investigates formal path expressions for directed triangulated grid graphs and king graphs by establishing optimal upper and lower bounds on expression length through decomposition techniques and algebraic-branching-program methods, while also linking path-polynomial factorizations to min-cuts and two-terminal reliability.