An efficient algorithm for characterization of cut-complexes. (English) Zbl 0766.06013
Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 85, 89-95 (1991).
[For the entire collection see Zbl 0747.00036.]
A subset \(C\) of the \(n\)-dimensional unit cube \(\{0,1\}^ n\) is a cut- complex if it is linearly separable, i.e., there exist \(b\in \mathbb{R}\), \(a\in\mathbb{R}^ n\) such that \(x\in C\) iff \(ax\geq b\) for every \(x\in\{0,1\}^ n\). A modified algorithm for generating non-isomorphic cut-complexes is presented and also some calculation-time comparisons with earlier algorithms.
A subset \(C\) of the \(n\)-dimensional unit cube \(\{0,1\}^ n\) is a cut- complex if it is linearly separable, i.e., there exist \(b\in \mathbb{R}\), \(a\in\mathbb{R}^ n\) such that \(x\in C\) iff \(ax\geq b\) for every \(x\in\{0,1\}^ n\). A modified algorithm for generating non-isomorphic cut-complexes is presented and also some calculation-time comparisons with earlier algorithms.
Reviewer: J.Henno (Naasa)
MSC:
| 06E30 | Boolean functions |
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 68Q25 | Analysis of algorithms and problem complexity |
