1. Combinatorial Scientific Computing: I am broadly interested in combinatorial optimization and development of parallel combinatorial (graph) algorithms for matching, coloring, clustering, extraction of chordal subgraphs, and network flow.
  2. Study of electric power grids : I am broadly interested in the research of combinatorial algorithms with applications to the study of electric power grids.
  3. Cyber security : Graph-theoretic approaches play a key role in cyber security. In this context, my research interests are in developing graph-theoretic methods for modeling and metrics, and applications in cyber system resilience.

Projects/Funding

Laboratory Directed Research and Development, Pacific Northwest National Laboratory (PI/Co-PI/Senior Personnel):


Synergistic Activities


Doctoral Thesis

Abstract: A matching M in a graph is a subset of edges such that no two edges in M are incident on the same vertex. Matching is a fundamental combinatorial problem with many applications. In the first part of this thesis, we develop exact and approximation algorithms for vertex weighted matchings, an under-studied variant of the weighted matching problem. We propose three exact algorithms, three half approximation algorithms, and a two-third approximation algorithm. We exploit inherent properties of this problem such as lexicographical orders, decomposition into sub-problems, and the reachability property, not only to design efficient algorithms, but also to provide simple proofs of correctness of the proposed algorithms. In the second part of this thesis, we describe work on a new parallel half-approximation algorithm for weighted matching. Algorithms for computing optimal matchings are not amenable to parallelism, and hence we consider approximation algorithms here. We extend the existing work on a parallel half approximation algorithm for weighted matching and provide an analysis of its time complexity. We support the theoretical observations with experimental results obtained with MatchBoxP, toolkit designed and implemented in C++ and MPI using modern software engineering techniques. The work in this thesis has resulted in better understanding of matching theory, a functional public-domain software toolkit, and modeling of the sparsest basis problem as a vertex-weighted matching problem.


Last updated: