Network instance Scale-free; varying vertex count, bounded induced width, edition 2

Scale-free graphs generated following the Barabási-Albert method, then selected for induced width. The weights of the constraint arcs are set such that at least one solution exists (i.e. the graph contains no negative cycles and the STN is consistent). This archive contains 160 graphs on 250–1000 vertices, 2176–3330 edges, upper bound on treewidth 150–200. The scale-free density parameter for this selection is 3–15. Parent item: Benchmark instances for experiments in ["Computing All-Pairs Shortest Paths by Leveraging Low Treewidth" (paper, 2012)]

本数据集包含的无标度图（scale-free graphs）均先通过巴拉巴西-阿尔伯特（Barabási-Albert）方法生成，随后基于诱导宽度（induced width）完成筛选。约束弧（constraint arcs）的权重被设置为确保至少存在一个可行解，即该图不含负环（negative cycles），且简单时序网络（STN）具备一致性。本数据集共包含160张无标度图，其顶点数介于250至1000之间，边数介于2176至3330之间，树宽（treewidth）上限为150至200。本次筛选所采用的无标度密度参数取值范围为3至15。本数据集的基准测试用例源自2012年发表的论文《通过利用低树宽计算全对最短路径》中的实验内容。