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
1985
0 references
algorithm
0 references
circuit design
0 references
hypergraph
0 references
computational complexity
0 references
0.9133358
0 references
0 references
0.90545523
0 references
0.8964373
0 references
0.8956653
0 references
0.8954858
0 references
0.8929291
0 references
0 references
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