scientific article; zbMATH DE number 1153451
A subset \(S\) of an ordered set \(P\) is called a cutset if each maximal chain of \(P\) has nonempty intersection with \(S\). If, in addition, \(S\) is also an antichain it is an antichain cutset. In this paper new characterizations and generalizations of these and related concepts are considered. The main generalization is replacing the ordered set \(P\) by a directed graph \(G=(V,E)\). In this case a cutset is a subset \(S\) of the vertex set \(V\) of \(G\) which meets each extremal path of \(G\). The main results of this paper include (a) a characterization, by means of a closure property, of those antichains which are cutsets; (b) a characterization, by means of ``forbidden paths in the graph, of those graphs which can be expressed as the union of antichain cutsets; (c) a simpler proof of an existing result about \(N\)-free orders; and (d) efficient algorithms for many related problems, such as constructing antichain cutsets containing or excluding specified elements or forming a chain. There is also included a brief discussion of the use of antichain cutsets in a parsing problem for LR(\(k\)) languages.
- Antichain cutsets of strongly connected posets
- Inversions, cuts, and orientations
- scientific article; zbMATH DE number 3957179 (Why is no real title available?)
- scientific article; zbMATH DE number 733226 (Why is no real title available?)
- Optimal tree-based one-time digital signature schemes
- Efficient Construction of 2-Chains with a Prescribed Boundary
- Cut-sets in infinite graphs and partial orders
- LS sets as cohesive subsets of graphs and hypergraphs
- Finite cutsets and finite antichains
- Cutsets and anti-chains in linear lattices
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388202)