Venue

The Workshop will be held in the Satish Dhawan Auditorium, Indian Institute of Science, Bangalore 560012.

Contact

  • Subir Kumar Ghosh (Convener), School of Technology & Computer Science, Tata Institute of Fundamental Research, Mumbai 400005.
Email-Id: igga[AT]tcs[dot]tifr[dot]res[dot]in

Background

The study of algorithms is at the very heart of computer science. In the last five decades, a number of significant advances have been made in the field of algorithms ranging from the development of faster algorithms to the startling discovery of some natural problems for which all algorithms are found to be inefficient. These results triggered considerable interest in the study of algorithms, and the area of algorithm design and analysis has evolved into a field of interest. Teaching and research in this foundational aspect of computing is therefore a natural and desirable thrust area. Hence, algorithmic studies form a major component of computer science programs in colleges and universities.

In the last four decades, graph and geometric problems have been studied by computer science researchers using the framework of analysis of algorithms. Graph theory is the study of the properties of graphs. Graph algorithms are one of the oldest classes of algorithms and they have been studied for almost 300 years. Graphs provide essential models for many applications areas of computer science, and at the same time, they are fascinating objects of study in pure and applied mathematics. There have been a number of exciting recent developments in graph theory that are important for designers of algorithms to know about. Correspondingly, the algorithmic viewpoint of computer science has stimulated much research in graph theory. Graph theory and graph algorithms are inseparably intertwined subjects. On the other hand, the main impetus for the development of geometric algorithms came from the progress in computer graphics, computer-aided design and manufacturing. In addition, algorithms are also designed for geometric problems that are classical in nature. The success of the field can be explained from the beauty of the geometry problems studied, the solutions obtained, and by the many application domains- computer graphics, geographic information systems, robotics and others, in which geometric algorithms play a crucial role.[Top]

Objectives

Graph and geometric algorithms are at the heart of many computer applications. So, it is expected that computer scientists and professional programmers know frequently used algorithms and generic techniques for efficient organization and retrieval of data, modeling, understanding and solving graph and geometric problems. This introductory workshop provides an opportunity to the participants for getting exposed to the field of graph and geometric algorithms, which may help them in future in solving graph and geometric problems and designing new algorithms. With this objective, graph and geometric theory and algorithms for some problems will be presented in the workshop by a distinguished panel of speakers.[Top]

Areas

Geometric Algorithms, Graph Algorithms, Graph Theory, Randomized Algorithms, Approximation Algorithms, Data Structures, Algorithmic Techniques, Computational Geometry, Combinatorial Geometry, Computer Graphics.[Top]

Participants

Teachers and students (undergraduate, post-graduate and doctoral) of Computer Science and Engineering are eligible to attend this workshop. Participants are expected to have taken introductory courses in Discrete Mathematics, Data Structures and Algorithms. Scientists and engineers working in research laboratories or industries with required background are also welcome to attend the workshop.[Top]

Benefits

Participants will be exposed to key tools and techniques in the field of graph and geometric algorithms. Speakers are key figures in their respective research areas, and the purpose of the workshop is to expose students, teachers, and professionals to various key developments in these research areas. This will benefit the participants in designing, analyzing and implementing complex software, especially arising in the field of robotics, geographical information systems, route planning, wireless and mobile networks. Workshop may lead to active collaboration between participants and resource persons in these areas.

Participants will be issued certificates for attending the workshop.[Top]

Coordinators

  • Subir Kumar Ghosh (Convener), School of Technology & Computer Science, Tata Institute of Fundamental Research,
    Mumbai 400005.
  • L. Sunil Chandran, Department of Computer Science & Automation, Indian Institute of Science, Bangalore 560012.
  • Vijay Natarajan, Department of Computer Science & Automation, Indian Institute of Science, Bangalore 560012.
  • Sathish Govindarajan, Department of Computer Science & Automation, Indian Institute of Science, Bangalore 560012.
    • [Top]

Course Outline (Tentative)

Algorithmic Paradigms:

  • Speaker: Venkatesh Raman, The Institute of Mathematical Sciences, Chennai.
    Topic: Fixed Parameter Algorithms.
  • Speaker: Partha Goswami, University of Calcutta.
    Topic: Duality Transformations in Geometry.
  • Speaker: Sandeep Sen, Indian Institute of Technology, Delhi.
    Topic: A Short Guided Tour of Randomized Algorithms.
  • Speaker: Swami Sarvattomananda, Ramakrishna Mission Vivekananda University, Belur.
    Topic: Prune-and-search Technique in Geometry.
  • Speaker: Daya Gaur, University of Lethbridge, Canada.
    Topic: Approximation Algorithms and Linear Programming.

Computational Geometry:

  • Speaker: Anil Maheshwari, Carleton University, Canada.
    Topic: Geometric Spanners.
  • Speaker: Sudebkumar Prasant Pal, Indian Institute of Technology, Kharagpur.
    Topic: Geometric Data Structures.
  • Speaker: Subhas Chandra Nandy, Indian Statistical Institute, Kolkata.
    Topic: Voronoi Diagrams.
  • Speaker: Sandip Das, Indian Statistical Institute, Kolkata.
    Topic: Geometric Facility Location Problems.
  • Speaker: Sathish Govindarajan, Indian Institute of Science, Bangalore.
    Topic: Geometric Graphs.

Computer Graphics and Vision:

  • Speaker: Sudeep Sarkar, University of South Florida, USA.
    Topic: Graphs and Object Recognition.
  • Speaker: Vijay Natarajan, Indian Institute of Science, Bangalore.
    Topic: Scalar Field Visualization.
  • Speaker: P. J. Narayanan, International Institute of Information Technology, Hyderbad.
    Topic: Graphics Processor Units: For Graphics and Beyond

Graph Algorithms:

  • Speaker: Surender Baswana, Indian Institute of Technology, Kanpur.
    Topic: Algorithms for Graph Spanners - Static, Dynamic and Fault Tolerant.
  • Speaker: Karunakaran Murali Krishnan, National Institute of Technology, Calicut.
    Topic: Graph Representation of Codes and Decoding Algorithms.
  • Speaker: C. R. Subramanian, The Institute of Mathematical Sciences, Chennai.
    Topic: Randomized Algorithms for Counting Problems.

Graph Theory:

  • Speaker: N. S. Narayanaswamy, Indian Institute of Technology, Chennai.
    Topic: Graph Classes with Interesting Structural Properties.
  • Speaker: Ajit A. Diwan, Indian Institute of Technology, Mumbai.
    Topic: Topological Minors of Graphs.
    • [Top]

Registration

  1. There is no registration fee.
  2. There is a limited number of accommodation available for outstation participants.
  3. Maximum of 225 applications will be selected for the workshop.
  4. Breakfast and Lunch will be provided free of cost to all participants at the workshop venue for all four days.
  5. All outstation teacher and student participants will be paid sleeper class return train fare.
  6. The Last Date of Registration : May 3, 2009.

Registration is closed.