COURSE OBJECTIVE
· To introduce the basics of graphs and combinatory required for VLSI design and Optimization.
COURSE CONTENT
Basic definitions, Degree of vertices, Complement of a graph. Self complementary graph, some eccentricity properties of graphs. Tree, spanning tree. Directed graphs standard definitions; strongly, weakly, unilaterally connected digraphs, deadlock communication network. Matrix representation of graph and digraphs. Some properties (proof not expected).
Eulerian graphs and standard results relating to characterization. Hamiltonian graph-standard theorems (Dirac theorem, Chavathal theorem, closure of graph).Non Hamiltonian graph with maximum number of edges. Self-centered graphs and related simple theorems. Chromatic number; Vertex and edge (only properties and examples)-application to colouring. Planar graphs, Euler’s formula, maximum number of edges in a planar graph. Five colour theorem.
DFS-BFS algorithm, shortest path algorithm, min-spanning tree and max-spanning tree algorithm, planarity algorithm. Matching theory, maximal matching and algorithms for maximal matching. Perfect matching (only properties and applications to regular graphs).
Flows in graphs, Ranking of participants in tournaments, simple properties and theorems on strongly connected tournaments. Application of Eulerian digraphs. PERT-CPM. Complexity of algorithms; P-NP- NPC-NP hard problems and examples.
Linear- Integer Linear programming, Conversion of TSP, maxflow, Knapsack scheduling, shortest path problems for Linear programming types - branch bound method to solve Knapsack problems- critical path and linear programming conversion- Floor shop scheduling problem- Personal assignment problem.
Dynamic programming- TSP- compartment problems- Best investment problems.
Text Books
1. C.Papadimitriou&K.Steiglitz, “Combinatorial Optimization”, Prentice Hall, 1982.
2. H.Gerez, “Algorithms for VLSI Design Automation”, John Wiley, 1999.
Reference Book
1. B.Korte&J.Vygen, “Combinatorial Optimization”, Springer-Verlag, 2000.
COURSE OUTCOMES
Students are able to
CO1: understand the various types of graph Algorithms and graph theory properties. CO2: analyse the NP – complete problems.
CO3: distinguish the features of the various tree and matching algorithms
CO4: appreciate the applications of digraphs and graph flow.
CO5: understand the linear programming principles and its conversion.
