Finding minimum generators of path systems (Q1305531): Difference between revisions

Let \(P\) be a simple directed path, and let \(\mathbb{P}\) be a system of distinct subpaths of \(P\). A system \(\mathbb{G}\) of subpaths of \(P\) is said to generate a path \(J\) if \(J\) is the union of some members of \(\mathbb{G}\), and \(\mathbb{G}\) generates \(\mathbb{P}\) if every member of \(\mathbb{P}\) is generated by \(\mathbb{G}\). The author gives an algorithmic proof, which relies on Dilworth's theorem, of a min-max theorem of Györi on generators of path systems.