
doi: 10.1007/bf02579138
A subset T of the node set V of a digraph \(G=(V,E)\) is called path-closed if for each v,v'\(\in T\) all nodes lying on directed paths from v to v' also belong to T. The author characterizes the convex hull of the incidence vectors of all path-closed sets by a set of linear inequalities thus turning the problem of finding a maximum path-closed set (in a graph with weighted vertices) into an LP, and he gives a fast algorithm for solving it. Some other results like a min-max-theorem on partitioning a given subset of V into a minimum number of path-closed sets and an analogue to Dilworth's theorem are also derived.
path-closed sets, Directed graphs (digraphs), tournaments, Programming involving graphs or networks, Paths and cycles, digraph
path-closed sets, Directed graphs (digraphs), tournaments, Programming involving graphs or networks, Paths and cycles, digraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
