ハイパーキューブの二分割コストについて

書誌事項

タイトル別名
  • On the costs of division of a hypercube into two parts

この論文をさがす

説明

ハイパーキューブの点集合を指定された個数の2つの部分に分割する問題を考察する.異なる部分に属する2点を結ぶ辺の本数と, それらの辺の端点の個数の2つを分割のコストと見なす.ハイパーキューブの点に優先順位を付け, それに従って点を取ることが第二のコストを最小化することを示す.この優先順位は, 重みが小さいほど高く, 同じ重みの点の間では対応する二進数が大きいほど高い.第一のコストを最小化する別の優先順位は既に知られている.この優先順位は, 対応する二進数が小さいほど高い.これらの優先順位がユークリッド空間上の超立方体を超平面で切断することにより得られることを示す.Kruskal-Katonaの定理の発展形と見なせる定理を示し, 基本的な道具として用いる.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1571417127361974144
  • NII論文ID
    110003180309
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ