No label defined (Q3337494)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3869363
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3869363 |
Statements
1984
0 references
broadcast network
0 references
irredundant set
0 references
0.7597262859344482
0 references
0.754548192024231
0 references
0.7492716312408447
0 references
[For the entire collection see Zbl 0534.00004.] The study of the problem ''what is the maximal number of senders having at least one site in range that receives its transmission'' in broadcast networks leads to a very special problem in the graph theory: having an undirected graph G(V,E) what is the maximum order of an open irredundant set OIR. Supposing N(v) denotes the set of vertices adjacent to v \((N(v)=\{u\in V:\) (u,v)\(\in E\})\) the OIR is such a set of vertices for which it holds: \[ (\forall v\in OIR)\quad (N(v)-\cup_{u\in OIR- \{v\}}(N(u)\cup\{u\}))\neq\emptyset. \] The algorithm computing the maximum order of an open irredundant set for trees as well as the proof of its correctness and comments concerning its algorithmical complexity are presented.
0 references