scientific article; zbMATH DE number 1153451

From MaRDI portal
Publication:4388202





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.











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)