Finding minimum generators of path systems
type: Item
instance of: scholarly article
title: Finding minimum generators of path systems
zbMATH Open document ID: 0938.05036
author: András Frank
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-06-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1346895
zbMATH Keywords: path systems
reviewed by: Michael Raines
MaRDI profile type: Publication
cites work: Q3292914
cites work: Q4263470
cites work: Minimal edge-coverings of pairs of sets
cites work: An algorithm for covering polygons with rectangles
cites work: Irredundant intervals
cites work: A weighted min-max relation for intervals
description: scientific article; zbMATH DE number 1346895