Path-closed sets
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.
- A decomposition theorem for partially ordered sets
- A generalization of max flow—min cut
- Anti-blocking polyhedra
- Blocking and anti-blocking pairs of polyhedra
- scientific article; zbMATH DE number 3691332 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- Lattice Polyhedra II: Generalization, Constructions and Examples
- Matroids and the greedy algorithm
- On total dual integrality
- Total dual integrality and integer polyhedra
- Lattice matrices, intersection of ring families and dicuts
- Optimum partitioning into intersections of ring families
- Switchdec polyhedra
- Finding a maximum-weight convex set in a chordal graph
- scientific article; zbMATH DE number 3910419 (Why is no real title available?)
- On switching paths polyhedra
- GLB-closures in directed acyclic graphs and their applications
This page was built for publication: Path-closed sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802569)
