| Title | : | Duality in Graphs and Algorithmic Implications |
| Speaker | : | K. Thulasiraman (Universtiy of Oklahoma) |
| Details | : | Mon, 13 Jun, 2016 11:00 AM @ BSB 361 |
| Abstract: | : | Duality plays a central role in different branches of mathematics, in particular, graph theory and combinatorial optimization ,and their engineering applications. In the context of graphs circuits and cuts are dual concepts. On the other hand, edge removal and edge contraction are dual operations. For engineering applications, these concepts and operations have had a profound impact on the development of computationally efficient techniques for engineering analysis and design. In the context of computer science , they have helped gain insight into the techniques of algorithm development and further generalizations. In this talk we shall illustrate these ideas with respect to the problem of designing a survivable routing of the edges of the logical topology of an IP- over -WDM optical network. The problem is to map each edge of the logical topology onto a path in the physical topology such that the logical topology remains connected after a single physical edge failure. The SMART approach (a structural methodology) developed by Kurant and Thiran of EPFL involves repeated selection of circuits in the logical topology, mappings and contractions of the circuit edges, until the logical topology collapses into a single node. We show how one can develop a dual approach called CUTSET-SMART , overcome the difficulties encountered and develop further generalizations leading to different variants of SMART with varying levels of capability to provide protection against multiple failures. Bio: Krishnaiyan Thulasiraman received the Bachelor’s degree (1963) and Master’s degree (1965) in Electrical Engineering from the University of Madras, India, and the Ph.D. degree (1968) in Electrical Engineering from IIT, Madras, India. He holds the Hitachi Chair and is Professor in the School of Computer Science at the University of Oklahoma, Norman, where he has been since 1994. Prior to joining the University of Oklahoma, Thulasiraman was professor (1981-1994) and chair (1993-1994) of the ECE Department in Concordia University, Montreal. He was on the faculty in the EE and CS departments of the IIT during 1965-1981. Dr. Thulasiraman’s research interests have been in graph theory, combinatorial optimization, algorithms and applications in a variety of areas in CS and EE: electrical networks, VLSI physical design, systems level testing, communication protocol testing, parallel/distributed computing, telecommunication network planning, fault tolerance in optical networks, interconnection networks etc. He has published extensively in archival journals, coauthored with M. N. S. Swamy two text books “Graphs, Networks, and Algorithms” (1981) and “Graphs: Theory and Algorithms” (1992), both published by Wiley Inter-Science, and authored two chapters in the Handbook of Circuits and Filters (CRC and IEEE, 1995) and a chapter on “Graphs and Vector Spaces” for the handbook of Graph Theory and Applications (CRC Press, 2003). Dr. Thulasiraman has received several awards and honors: 2006 IEEE Circuits and Systems Society Technical Achievement Award. Endowed Gopalakrishnan Chair Professorship in CS at IIT, Madras (Summer 2005), Elected Member of the European Academy of Sciences (2002), IEEE CAS Society Golden Jubilee Medal (1999), Fellow of the IEEE (1990) and Senior Research Fellowship of the Japan Society for Promotion of Science (1988). He has held visiting positions at the Tokyo Institute of Technology, University of Karlsruhe, University of Illinois at Urbana-Champaign and Chuo University, Tokyo. Dr. Thulasiraman has been Vice President (Administration) of the IEEE CAS Society (1998, 1999), Technical Program Chair of ISCAS (1993, 1999), Deputy Editor-in-Chief of the IEEE Transactions on Circuits and Systems I ( 2004-2005), Co-Guest Editor of a special issue on "Computational Graph Theory: Algorithms and Applications" (IEEE Transactions on CAS , March 1988), , Associate Editor of the IEEE Transactions on CAS (1989-91, 1999-2001), and Founding Regional Editor of the Journal of Circuits, Systems, and Computers. Recently, he founded the Technical Committee on “Graph theory and Computing” of the IEEE CAS Society and has been a founding member of the editorial board of the AKCE International Journal of Graphs and Combinatorics. |
