m、kを正整数とするとき、次数m、高さkの完全木構造接続をもつグラフを考える。1次元等間隔格子上に、根を左端に固定して区間配線長をなるべく小さくするように根以外の各節点を配置する。任意のm、kについて最大区間長を最小にする節点配置が存在することを示し、更にこれを具体的に求める方法を示す。
国際短期大学情報ネットワーク学科