Document Open Access Logo

Simplifying Activity-On-Edge Graphs

Authors David Eppstein, Daniel Frishberg , Elham Havvaei

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.24.pdf
  • Filesize: 0.81 MB
  • 14 pages

Document Identifiers

Author Details

David Eppstein
  • University of California, Irvine, CA, United States
Daniel Frishberg
  • University of California, Irvine, CA, United States
Elham Havvaei
  • University of California, Irvine, CA, United States

Funding

This work was supported in part by NSF grants CCF-1618301 and CCF-1616248.

Cite As Get BibTex

David Eppstein, Daniel Frishberg, and Elham Havvaei. Simplifying Activity-On-Edge Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.24

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • directed acyclic graph
  • activity-on-edge graph
  • critical path
  • project planning
  • milestone minimization
  • graph visualization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sarmad Abbasi, Patrick Healy, and Aimal Rextin. Improving the running time of embedded upward planarity testing. Information Processing Letters, 110(7):274-278, 2010. URL: https://doi.org/10.1016/j.ipl.2010.02.004.
  2. A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM J. Comput., 1(2):131-137, 1972. URL: https://doi.org/10.1137/0201008.
  3. C. Alexander, D. Reese, and J. Harden. Near-critical path analysis of program activity graphs. In Proceedings of International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pages 308-317. IEEE, 1994. URL: https://doi.org/10.1109/mascot.1994.284406.
  4. David Arditi and Thanat Pattanakitchamroon. Selecting a delay analysis method in resolving construction claims. International J. Project Management, 24(2):145-155, 2006. URL: https://doi.org/10.1016/j.ijproman.2005.08.005.
  5. Oliver Bastert and Christian Matuszewski. Layered drawings of digraphs. In Michael Kaufmann and Dorothea Wagner, editors, Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science, pages 87-120. Springer-Verlag, 2001. URL: https://doi.org/10.1007/3-540-44969-8_5.
  6. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR, 1998. Google Scholar
  7. Pranay Chaudhuri and Ratan K. Ghosh. Parallel algorithms for analyzing activity networks. BIT, 26(4):418-429, 1986. URL: https://doi.org/10.1007/bf01935049.
  8. Giuseppe Di Battista, Roberto Tamassia, and Ioannis G. Tollis. Area requirement and symmetry display of planar upward drawings. Discrete and Computational Geometry, 7(4):381-401, 1992. URL: https://doi.org/10.1007/BF02187850.
  9. David Eppstein and Joseph A. Simons. Confluent Hasse diagrams. J. Graph Algorithms Appl., 17(7):689-710, 2013. URL: https://doi.org/10.7155/jgaa.00312.
  10. Ashim Garg and Roberto Tamassia. Upward planarity testing. Order, 12(2):109-133, 1995. URL: https://doi.org/10.1007/BF01108622.
  11. Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601-625, 2001. URL: https://doi.org/10.1137/S0097539794277123.
  12. Patrick Healy, Ago Kuusik, and Sebastian Leipert. A characterization of level planar graphs. Discrete Math., 280(1-3):51-63, 2004. URL: https://doi.org/10.1016/j.disc.2003.02.001.
  13. Patrick Healy and Nikola S. Nikolov. Hierarchical Graph Drawing. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, pages 409-453. CRC Press, 2014. Google Scholar
  14. Jerry L. Householder and Hulan E. Rutland. Who owns float? J. Construction Engineering and Management, 116(1):130-133, 1990. URL: https://doi.org/10.1061/(ASCE)0733-9364(1990)116:1(130).
  15. Wei Huang and Lixin Ding. Project-scheduling problem with random time-dependent activity duration times. IEEE Transactions on Engineering Management, 58(2):377-387, 2011. URL: https://doi.org/10.1109/tem.2010.2063707.
  16. Michael Jünger and Sebastian Leipert. Level Planar Embedding in Linear Time. In Jan Kratochvıl, editor, Graph Drawing: 7th International Symposium, volume 1731 of Lecture Notes in Computer Science, pages 72-81. Springer-Verlag, 1999. URL: https://doi.org/10.1007/3-540-46648-7_7.
  17. Vidyadhar G. Kulkarni. A compact hash function for paths in PERT networks. Operations Research Letters, 3(3):137-140, 1984. URL: https://doi.org/10.1016/0167-6377(84)90005-1.
  18. Donald G. Malcolm, John H. Roseboom, Charles E. Clark, and Willard Fazar. Application of a technique for research and development program evaluation. Operations Research, 7(5):646-669, 1959. URL: https://doi.org/10.1287/opre.7.5.646.
  19. Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems, Man, and Cybernetics, 11(2):109-125, 1981. URL: https://doi.org/10.1109/TSMC.1981.4308636.
  20. Zhenming Xu. Automatic layout of information in the AOE network. In 2010 International Conference on Mechanic Automation and Control Engineering. IEEE, June 2010. URL: https://doi.org/10.1109/mace.2010.5536213.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact