The Recognition of Tolerance and Bounded Tolerance Graphs
Authors: George B. Mertzios, Ignasi Sau, Shmuel Zaks
http://arxiv.org/abs/1001.3251
Toleranceグラフの認識問題が多項式時間で解けるかどうかは大きな未解決問題だったけども,この論文ではそれがNP困難であることを証明している.
Authors: George B. Mertzios, Ignasi Sau, Shmuel Zaks
http://arxiv.org/abs/1001.3251
Toleranceグラフの認識問題が多項式時間で解けるかどうかは大きな未解決問題だったけども,この論文ではそれがNP困難であることを証明している.