On the costs of division of a hypercube into two parts
-
- Jimbo Shuji
- Department of Information Technology, Faculty of Engineering, Okayama University
-
- Hashiguchi Kosaburo
- Department of Information Technology, Faculty of Engineering, Okayama University
Bibliographic Information
- Other Title
-
- ハイパーキューブの二分割コストについて
Search this article
Description
Problems of dividing the vertex-set of a hypercube into two parts are discussed. The number of the edges that join the distinct parts and the number of the vertices that are endvertices are regarded as two costs of the division. A priority between the vertex-set is presented, and it is shown that taking vertices according to the priority minimizes the second cost. Another priority that minimizes the first cost is already known. It is shown that the priorities above are obtained by cutting the corresponding cube in a Euclidean space with a hyperplain. A theorem that can be regarded as an extension of the Kruskal-Katona theorem is presented, and used as a basic tool.
Journal
-
- IEICE technical report. Theoretical foundations of Computing
-
IEICE technical report. Theoretical foundations of Computing 98 (562), 25-32, 1999-01-23
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1571417127361974144
-
- NII Article ID
- 110003180309
-
- NII Book ID
- AN10013152
-
- Text Lang
- ja
-
- Data Source
-
- CiNii Articles
