Narrowness, pathwidth, and their application in natural language processing (Q1186169)

Let \(G=(V,E)\) be an ordered graph and \((v_ 1,\dots,v_ n)\) be the sequence of vertices, going through the shack (a storage unit with the condition that a vertex can be moved from the shack only if all the vertices connected to it are also in the shack or already were moved out). The maximum number of vertices in the shack is \(m(v_ 1,\dots,v_ n)\) and the minimum value of \(m(v_ 1,\dots,v_ n)\) taken over all permutations of the vertex set \(V\) is named the narrowness of \(G\). It is proved that the narrowness is equal to the pathwidth of \(G\) minus 1. The trees with the given narrowness are described.