抄録

○神保秀司（岡山大）・山本博章（信州大）

本論文では，有向グラフGで各辺に重みが，各点に点許容値が付いているものに対して，与えられた条件を満たすGの点の順列を求める問題を扱う．Gの点の順列が満たすべき条件として各点vについて，vに接続する有向辺eの重みとvにおける点許容値からなる不等式をいくつかの自然な形で統一的に与え，それらをGに対する許容条件と呼び，許容条件を満たすGの点の順列を求める問題を許容条件付き位相的整列問題と呼ぶことにする．本論文では，辺重みおよび点許容値付き単純有向グラフに対する許容条件をいくつか提案し，それらに対する許容条件付き位相的整列問題がある場合に線形時間で解け，かつ，ある場合にはNP完全であることを示す．