How many steps are necessary to separate a bigraph? (Q1850581)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: How many steps are necessary to separate a bigraph? |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | How many steps are necessary to separate a bigraph? |
scientific article |
Statements
How many steps are necessary to separate a bigraph? (English)
0 references
10 December 2002
0 references
The author presents a method to construct bigraphs in order to prove the following simple results: (1) There exist bigraphs that are deterministically separable, but in no less than \(n\) steps, for any \(n\in\mathbb{N}\). (2) There exist bigraphs that are non-deterministically separable, but in no less than 3 steps. For basis see \textit{D. Beaver}, \textit{S. Haber} and \textit{P. Winkler} [The mathematics of Paul Erdős, Vol. II, 121--135 (Algorithms Comb. 14, Springer, Berlin) (1997; Zbl 0892.05044)].
0 references
