ベンチマーク問題集には、以下のように様々の種類の問題が用意されている。
ランダムに生成 : Long-C、Long-n、Random4-C、Random4-n、Square-C、Square-n
道路ネットワーク : USA-road-d、USA-road-t
ここで USA-road-d や USA-road-t は以前からかなり使用させてもらっているが、道路ネットワークになっている。TIGER/Line による交差点をノード、その間の距離を枝長としたデータをグラフデータに直し、実際に解けるように変換したものだ。
*-C となっているものは、1048576 nodes 4063200 arcs のグラフに対し、最大枝数を 4^X (X=[0, 15]) として与えられている。最も大きいものは Long-C.15.0.gr や Random4-C.15.0.gr や Square-C.15.0.gr といったグラフで、最大枝長は 1G (10 億) にも及ぶ。また *-n は、点数・最大枝数の大きさを 2^X (X=[14, 20])、枝数はその４倍程になっている。いまだにグラフ特性が良く分かっていないので、分かり次第載せていく。
ランダムに生成 : Long-C、Long-n、Random4-C、Random4-n、Square-C、Square-n
道路ネットワーク : USA-road-d、USA-road-t
ここで USA-road-d や USA-road-t は以前からかなり使用させてもらっているが、道路ネットワークになっている。TIGER/Line による交差点をノード、その間の距離を枝長としたデータをグラフデータに直し、実際に解けるように変換したものだ。
*-C となっているものは、1048576 nodes 4063200 arcs のグラフに対し、最大枝数を 4^X (X=[0, 15]) として与えられている。最も大きいものは Long-C.15.0.gr や Random4-C.15.0.gr や Square-C.15.0.gr といったグラフで、最大枝長は 1G (10 億) にも及ぶ。また *-n は、点数・最大枝数の大きさを 2^X (X=[14, 20])、枝数はその４倍程になっている。いまだにグラフ特性が良く分かっていないので、分かり次第載せていく。