论文标题
在计算最佳线性图上
On Computing Optimal Linear Diagrams
论文作者
论文摘要
线性图是通过将元素表示为列，并以一个或多个水平线线段为行，将基于集的数据可视化的有效方法，其垂直重叠与其他行指示了集合的交叉点及其包含的元素。线性图的功效在很大程度上取决于几个线段的段。潜在的最小化问题已经通过启发式探索，但其计算复杂性尚未被分类。在本文中，我们表明，在线性图中最小化线段的线段等效于一个良好的NP - 硬性问题，并将NP硬度扩展到受限制的设置。我们开发了用于计算最小数量的线性片段数量的线性图的新算法，这些线段数量是在旅行销售人员（TSP）公式上构建的，并允许对元素订单的约束，即迫使两组迫使两个线段作为单线线段绘制为单个线段，并可以通过PQ-trees进行层次构造，并允许层次约束。我们进行了实验评估，并比较了以前的算法，以最大程度地将线段段与我们的TSP公式进行比较，这表明最先进的TSP-Solver可以最佳地解决所有考虑的实例，其中大多数在几毫秒内。
Linear diagrams are an effective way to visualize set-based data by representing elements as columns and sets as rows with one or more horizontal line segments, whose vertical overlaps with other rows indicate set intersections and their contained elements. The efficacy of linear diagrams heavily depends on having few line segments. The underlying minimization problem has already been explored heuristically, but its computational complexity has yet to be classified. In this paper, we show that minimizing line segments in linear diagrams is equivalent to a well-studied NP-hard problem, and extend the NP-hardness to a restricted setting. We develop new algorithms for computing linear diagrams with minimum number of line segments that build on a traveling salesperson (TSP) formulation and allow constraints on the element orders, namely, forcing two sets to be drawn as single line segments, giving weights to sets, and allowing hierarchical constraints via PQ-trees. We conduct an experimental evaluation and compare previous algorithms for minimizing line segments with our TSP formulation, showing that a state-of-the art TSP-solver can solve all considered instances optimally, most of them within few milliseconds.
