Simplifying Activity-On-Edge Graphs

DOI10.4230/LIPICS.SWAT.2020.24MaRDI QIDQ6059189zbMATH OpenOpenAlexFDO

Authors David Eppstein, Daniel Frishberg, Elham Havvaei

Publication date 2 November 2023

Full work available at URL https://arxiv.org/abs/2002.01610

zbMATH Keywords

directed acyclic graphgraph visualizationcritical pathproject planningactivity-on-edge graphmilestone minimization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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.

This page was built for publication: Simplifying Activity-On-Edge Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6059189)