MC558 - Design and Analysis of Algorithms II

Programme:

    1. Graphs

     - Definition  and representation of graphs and digraphs

     - Isomorphism

     - Neighborhood, cuts and degree

     - Paths and cycles

     - Subgraphs

     - Connected graphs and connected components

     - Independent sets, cliques and covers

     - Vertex coloring

     - Matching

     - Edge coloring

   2. Graphs algorithms

   - representation by lists of adjacency and by matrix adjacency

   - depth-first search

   - breadth-first search

   - topological sorting

   - strongly connected components

   - minimum spanning tree: greedy algorithms of Prim and Kruskal (use of "union-find" e  amortized analysis)

   - single-source shortest paths: algorithms of Dijkstra, Bellman-Ford  and DAG

   - all-pairs shortest paths: algorithms of matrix multiplication and Floyd-Warshall

 

 

 

3. Reduction between problems

- For obtaining  upper bounds

        - For obtaining lower bounds

        - Reductions between problems involving graphs

4. Linear Programming 

- Formulation of problems as LPs.