Research and Teaching Interests
My research interests lie in combinatorics and theoretical computer science. More specifically, I am interested in combinatorial design theory, graph theory, and the design and analysis of efficient and approximation algorithms for combinatorial optimization problems. If you are interested in my papers click here. If you are interested in some of my other writings, click here.
In the study of combinatorial designs, I am interested in mainly Steiner triple system, BIBDs, difference sets and covering designs. I have worked on projects that involved enumeration of all non-isomorphic designs with certain parameters, studied whether certain combinatorial designs exists. I have also studied properties of certain classes of designs such as friendship 3-hypergraphs and Sperner partition systems.
In my study of graphs, I am mainly interested in studying combinatorial optimization problems such as vertex cover and matchings. I am interested in developing approximation algorithms for NP-Hard problems. I am also interested in hardness of approximation of various NP-Hard problems. Finally I am interested studying subclasses of NP-Hard problems for which the subclasses are polynomial-time solvable.
Here are my (submitted, accepted and published) articles from 2006 to current.
- Guarding orthogonal terrains, with S. Durocher and S. Mehrabi (2015). Submitted.
- Cycle-maximal triangle-free graphs, with S. Durocher, D.S. Gunderson, M. Skala. Discrete Mathematics 338(2015), 274-290.
- A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph, with G.H.J. van Rees. Australian Journal of Combinatorics 57(2013),73-78.
- Friendship 3-hypergraphs, with G.H.J. van Rees, S. H. Seo, and N.M. Singhi. Discrete Mathematics 312 (2012), 1892-1899.
- Sperner partition systems, with Karen Meagher. Accepted to appear in Journal of Combinatorial Designs (Accepted on July 19, 2012 and published online August 16, 2012).
- Combination labelings of graphs. Applied Mathematics E-Notes, 12(2012), 158-168.
- Cool-lex Order and k-ary Catalan Structures with Stephane Durocher, Debajyoti Mondal, Frank Ruskey, and Aaron Williams. Journal of Discrete Algorithms, special issue of invited papers selected from the Twenty-Second International Workshop on Combinatorial Algorithms (IWOCA 2011). 16(2012), 287-307.
- A note on the Pancylism of block intersection graphs of universal-friend friendship hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 83(2010) 65-75.
- Antimagic labelings of power of cycles graphs. Accepted to Ars Combinatoria (July.23, 2011)
- Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order, with S. Durocher, D. Mondal, and A. Williams. In proceedings of the Twenty-Second International Workshop on Combinatorial Algorithms (IWOCA 2011). Springer Lecture Notes in Computer Science, 7056(2011), 182-194. 2011.
- Savate-Beam Triple Systems for v=5 and v=6, with D.W. Hein. Journal of Combinatorial Mathematics and Combinatorial Computing, 57(2011), 161-168.
- The Stein_Lovasz Theorem and its Application to Some Combinatorial Arrays, with D. Deng, Y. Zhang, G.H.J. van Rees. Journal of Combinatorial Mathematics and Combinatorial Computing, 77(2011), 17-32.
- Maximum Leaf Spanning Trees for Grid Graphs, with M. Toulouse. Journal of Combinatorial Mathematics and Combinatorial Computing, 73(2010) 181-193.
- Degree sequence conditions for partial Steiner triple systems, with M.S. Keranen, D.L. Kreher, W.H. Kocay. Bulletin of the ICA, 57(2009) 71-73.
- A Multilevel Cooperative Tabu Search Algorithm for the Covering Design Problem, with C. Dai, M. Toulouse. Journal of Combinatorial Mathematics and Combinatorial Computing, 68(2009) 33-66.
- Mutually Nearly Orthogonal Latin Squares, with G.H.J. van Rees. Journal of Combinatorial Mathematics and Combinatorial Computing, 62(2007) 13-24.
- On 3-Hypergraphs with Equal Degree Sequences, with W.L.Kocay. Ars Combinatoria, 82(2007) 145-157.
- Constructions and Bounds for (m,3)-Splitting Systems. Discrete Mathematics, with D. Deng, D.R. Stinson, G.H.J. van Rees, R. Wei. 307(2007), 18-37.
- There is no (22,8,4) Block Design, with R.T. Bilous, C.W.H. Lam, L.H. Thiel, G.H.J. van Rees,S.P. Radziszowski, W.H. Holzmann, H. Kharaghani. Journal of Combinatorial Designs, 15 (2007) 262-267.
- Constructions of 2-Cover-Free Families and Related Separating Hash Families, with G.H.J. van Rees, R. Wei. Journal of Combinatorial Designs, 14(2006), 423-440.
- Variations of the Maximum Leaf Spanning Tree Problem for Bipartite Graphs, with M. Toulouse. Information Processing Letters, 97(2006),129-132.
- Covering Designs on 13 Blocks, with M. Greig, G.H.J. van Rees. Utilitas Math. 70(2006) 221-261.
- Some NP-Completeness Results on Partial Steiner Triple Systems and Parallel Classes, with M. Toulouse. Ars Combinatoria 80(2006) 45-51.
- A Cooperative Multilevel Tabu Search Algorithm for the Covering Design Problem, with C. Dai,M. Toulouse. LNCS 3871(2006), 119-130.
- Lotto Designs (pages 529-536), with G.H.J. van Rees. The CRC Handbook of Combinatorial Designs, 2nd Edition(2006)
- On {123,124,134}-free systems, with D.R. Stinson, G.H.J. van Rees and R. Wei. Congressus Numerantium , V183 (2006) 161-174.
Here are some of my writings on various CS/mathematics topics. Most of these are just explanations on known results that I am interested in.
Interesting Links
Here is an article by Erza Brown on various interpretations of a Steiner triple system of order 7.
Service
I have served on various committees while employed at the University of Manitoba. A listing of these committees is given below.
- Associate head of Compute Science (undergraduate studies)
- Computer Science hiring committee
- Graduate studies committee
- Undergraduate curriculum committee
- Industry liaison committee
- Faculty of Science executive committee
- Faculty of Science committee on courses and programs (COCAP)
- Faculty of Science tenure and promotion committee
I have also been a reviewer for various journals and served on numerous M.Sc. and Ph.D. examining committees.
Courses taught
Current Courses
I will teaching a graduate course in combinatorial optimization in Winter (January to April) 2016.
Courses Taught
Below is a listing of courses that I have taught at least once while employed at the University of Manitoba.
- COMP 1010 – Introduction to Computer Science
- COMP 2080 – Analysis of Algorithms
- COMP 2130 – Discrete Mathematics for Computer Science
- COMP 2140 – Data Structures and Algorithms
- COMP 2160 – Programming Practices
- COMP 2280 – Introduction to Computer Systems
- COMP 3170 – Analysis of Algorithms and Data Structures
- COMP 3290 – Introduction to Compiler Construction
- COMP 3720 – Computer Networks
- COMP 4140 – Introduction to Cryptography and Crypto-systems
- COMP 7720 – Approximation Algorithms
- COMP 7720 – Combinatorial Algorithms
- COMP 7720 – Combinatorial Optimization