Path-closed sets |
| |
Authors: | Heinz Gröflin |
| |
Institution: | (1) Institut für Operations Research, ETH-Zentrum, CH-8092 Zürich, Switzerland |
| |
Abstract: | Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR
v
, using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the
problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s
theorem. |
| |
Keywords: | 05 C 20 05 C 38 06 A 10 52 A 25 90 B 10 90 C 05 |
本文献已被 SpringerLink 等数据库收录! |
|