Advanced Graph Theory

Dr. Rajiv Misra is an Associate Professor in Department of Computer Science and Engineering at Indian Institute of Technology Patna, India. He obtained his Ph.D degree from IIT Kharagpur, M.Tech degree in Computer Science and Engineering from the Indian Institute of Technology (IIT) Bombay, and Bachelor's of engineering degree in Computer Science from MNIT Allahabad. His research interests spanned a design of distributed algorithms for Mobile,Adhoc and Sensor Networks, Distributed Cloud Computing and Wireless Networks. He has contributed significantly to these areas and published more than 60 papers in high quality journals and conferences, and 2 book chapters. His h-index is 9 with more than 500 citations.He has authored papers in IEEE Transactions on Mobile Computing, IEEE Transaction on Parallel and Distributed Systems, Adhoc Networks, Journal of Parallel and Distributed Computing. He is currently editing a book titled as “Smart Techniques for a Smarter Planet:Towards Smarter Algorithms” for the Studies in Fuzziness and Soft Computing book series,Springer (2017). He has supervised three Phds and currently four Phds are ongoing in his supervision in the area of cloud computing, cyber-physical systems, distributed computing,large scale data computing. He is a senior member of the IEEE and fellow of IETE. Recently he has been approved with IMPRINT-MHRD Sponsored Research Project title “Smart Weather: Location based Deep weather event prediction using spatial big data computing”. He has completed as the Principal Investigator of R&D Project Sponsored by DeiTY entitled as “Vehicular Sensor and Mesh Networks based Future ITS”. He has mentored the online course on Distributed Systems in the platform of NPTEL MOOC (Massive Open Online course). In this MOOC course, he has covered an in-depth understanding of fundamental principles and models underlying the theory, algorithms, and systems aspects of distributed computing. He has also covered few emerging topics such as peer-to- peer computing, distributed hash table, Google File System (GFS), HDFS, spark, sensor networks and security in distributed systems for significant impact. His graduated Phd students are currently working as Assistant Professors in BITs-Goa, NIIT-University and JIIT-University. 

COURSE LAYOUT:

Week 1  : Introduction to Graphs & its Applications, Basics of Paths, Cycles, and Trails, Connection, Bipartite Graphs, Eulerian Circuits, Vertex Degrees and Counting, Degree-sum formula, The Chinese Postman Problem and Graphic Sequences.
Week 2 : Trees and Distance, Properties of Trees, Spanning Trees and Enumeration, Matrix-tree computation, Cayley's Formula, Prufer code.
Week 3  : Matchings and Covers, Hall's Condition, Min-Max Theorem, Independent Sets, Covers and Maximum Bipartite Matching, Augmenting Path Algorithm, Weighted Bipartite Matching, Hungarian Algorithm.

Week 6  : Vertex Coloring and Upper Bounds, Brooks’ Theorem and Color-Critical Graphs, Counting Proper Colorings.
Week 7  : Planar Graphs, Characterization of Planar Graphs, Kuratowski's Theorem, Wagner's Theorem.

Week 8  : Line Graphs and Edge-coloring, Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness, Dominating Sets.

SUGGESTED READING MATERIALS:

1. D.B. West, Introduction to Graph Theory, Prentice Hall, 2001
   
2. Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005
   
3. J.A.Bondy and U.S.R.Murty: Graph Theory, Springer, 2008.
   
4. R.Diestel: Graph Theory, Springer( low price edition) 2000.
   
5. F.Harary: Graph Theory, Narosa, (1988)
   
6. C. Berge: Graphs and Hypergraphs, North Holland/Elsevier, (1973)