Topic outline

  • Περιεχόμενα μαθήματος

  • Σημειώσεις προερχόμενες από εργασίες φοιτητών

    • Depth First Search (DFS), DFS algorithm, parenthesis theorem, edge classification, directed acyclic graphs, topological numberings and sortings, single source shortest path, single source longest path, Bellman Ford algorithm, all pairs shortest paths, Program Evaluation and Review Technique (PERT).

    • Numbering directed acyclic graphs, properties of planar acyclic digraphs, tessellation representations, plane tessellation representation, sphere tessellation representation, visibility representations, constrained visibility representation, polyline drawings.

    • st-orientation / bipolar orientation, Even - Tarjan algorithm, a streamlined depth-first search algorithm, an algorithm for direct st-orientation computation - STN algorithm.

    • Circular graph drawing, Circular Drawing on a single embedding circle, Circular algorithm, circular drawings of nonbiconnected graphs on multiple embedding circles, circular-with radial algorithm, circular drawing of user defined groups on multiple embedding circles.

    • Euler paths and circuits, the Konisberg Bridge problem, Euler's theorem, Fleury's algorithm, Eulerization and semi-Eulerization, Hamilton paths and circuits, algorithm for finding a Hamilton circuit, Hamilton paths and circuits in directed graphs, Travelling salesman problem.