The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.24
URN: urn:nbn:de:0030-drops-122718
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12271/
Go to the corresponding LIPIcs Volume Portal

Eppstein, David ; Frishberg, Daniel ; Havvaei, Elham

Simplifying Activity-On-Edge Graphs

pdf-format:
LIPIcs-SWAT-2020-24.pdf (0.8 MB)

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 an O(mn²)-time algorithm for solving this graph minimization problem.

BibTeX - Entry

@InProceedings{eppstein_et_al:LIPIcs:2020:12271,
  author =	{David Eppstein and Daniel Frishberg and Elham Havvaei},
  title =	{{Simplifying Activity-On-Edge Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12271},
  URN =		{urn:nbn:de:0030-drops-122718},
  doi =		{10.4230/LIPIcs.SWAT.2020.24},
  annote =	{Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization}
}

Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI