General Program and Registration Information
Summer School on Graph Theory and Graph Algorithms
Dates: June 26, 2017 to July 15, 2017
Venue: Indian Institute of Technology Gandhinagar
Course Contents: Graph Theory: topics in structural graph theory, connectivity, graph minors, flows, graph decompositions, special graph classes (interval, circular arc, chordal, split, threshold, planar, etc). Graph Algorithms: elementary graph algorithms (traversal, flows, shortest paths, APSP), approximation and parameterized algorithms and dynamic graph algorithms.
Abstract: Graph theory is a classical area of research that examines mathematical structures used to model pairwise relations between objects. Graphs turn out to be a very versatile tool for modelling various application scenarios, including, but not limited to, computational biology, computational neuroscience, communication network design, VLSI-design, traffic optimisation, route planning, computer vision, network visualisation, and so on. Both the structural and algorithmic aspects of graph theory are fundamental to these application scenarios.
The objective of this summer school is to provide a forum for learning and discussing several foundational aspects of structural graph theory, interleaved with perspectives from algorithmic graph theory. Even traditionally, there has been a strong interplay between these two broadly defined aspects of graph theory: structural results are often exploited to design efficient algorithms, and on the other hand, many structural insights are obtained by procedural proofs which have an algorithmic flavour. The lectures in this school are designed to provide exposure to both these aspects, and also emphasizes engineering aspects by having lab sessions where participants will implement several of the algorithms that they encounter, understand benchmarking techniques and explore real-world data sets.
- Bireswar Das, IIT Gandhinagar
- Anirban Dasgupta, IIT Gandhinagar
- Manoj Gupta, IIT Gandhinagar
- Neeldhara Misra, IIT Gandhinagar
- Rahul Muthu, DAIICT
The course requires an understanding of elementary discrete mathematics and probability, and basic proof techniques in mathematics (such as induction, the pigeon-hole principle, double counting, etc). For the labs, familiarity with a programming language like Python is desirable. A first course in algorithms would be useful but not essential, as long as there is familiarity with basic notions of asymptotic functions (such as notions of big-O and Theta).