Graph Theory and Discrete Optimization (3 - 0 - 0) 4


·    To introduce the basics of graphs and combinatory required for VLSI design and Optimization.



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.



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.