论文标题
简化在边缘的活动图
Simplifying Activity-on-Edge Graphs
论文作者
论文摘要
我们正式化了用于可视化项目计划的活动的简化，在该图表中，图表的顶点代表项目里程碑，而边缘代表项目的任务或里程碑之间的时序约束。在此框架中，可以将项目的时间表构造为图形的平均图，其中顶点的级别代表每个里程碑计划发生的时间。我们专注于以下问题：给定一个代表项目的活动图表，找到等效的在边缘图（一个具有相同临界路径），该图具有最小数量的里程碑顶点。我们提供了一种多项式时间算法来解决此图最小化问题。
We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph (one with the same critical paths) that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide a polynomial-time algorithm for solving this graph minimization problem.
