Solution of one problem of optimal partition of the vertex set of a hypergraph (Q3752416)

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 3989392
Language Label Description Also known as
default for all languages
No label defined
    English
    Solution of one problem of optimal partition of the vertex set of a hypergraph
    scientific article; zbMATH DE number 3989392

      Statements

      Solution of one problem of optimal partition of the vertex set of a hypergraph (English)
      0 references
      0 references
      0 references
      1985
      0 references
      algorithm
      0 references
      circuit design
      0 references
      hypergraph
      0 references
      computational complexity
      0 references
      An algorithm is given to solve the following problem, which arises from the circuit design problem: For a given hypergraph H with kL vertices, find a partition of the vertex set of H into L equal subsets \(\{U^ k_ i\); \(i=1,2,...,L\}\) such that the sum \(\sum^{L}_{i=1}\mu (U^ k_ i)\) is maximized, where \(\mu (U^ k_ i)\) is the sum \(\sum_{v}(| U^ k_ i\cap v| -1)\) taken over all edges v of H with \(U^ k_ i\cap v\neq \emptyset.\) The author does not give a theoretic analysis of the computational complexity of an algorithm, but examples are given to show that the algorithm has an acceptable computational complexity for practical problems. Variations of this problem are also considered.
      0 references

      Identifiers