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

      0 references
      0 references
      1984
      0 references
      broadcast network
      0 references
      irredundant set
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references