Christine Cheng

Christine Cheng

  • Associate Professor, Computer Science

View Dr. Cheng's website.

Dr. Cheng’s general interests lie at the intersection of computer science and discrete mathematics, especially in algorithm design, combinatorial optimization, combinatorics, and graph theory. The main research focus is “stable matchings,” a solution concept used to match medical residents to hospital programs, students to schools, or kidneys to kidney patients.


  • PhD, Johns Hopkins University, 1999
  • MS, Johns Hopkins University, 1996
  • BS, University of the Philippines, 1994

Research Interests

  • Algorithm Design
  • Graph Algorithms
  • Combinatorial Optimization
  • Graph Theory
  • Combinatorics


  • C. Cheng, A. McConvey, D. Onderko, N. Shar, C. Tomlinson, Beyond knights and knaves, WG 2013.
  • C. Cheng and E. McDermid, Maximum Locally Stable Matchings, Algorithms 2013, 6(3), 383-395. A preliminary version of this paper appeared in MATCH-UP 2012.
  • C. Cheng, A Poset-based Approach to Embedding Median Graphs in Hypercubes and Lattices, Order 29 (2012), pp. 147--163.
  • C. Cheng, E. McDermid, I. Suzuki, The center stable matchings and the centers of cover graphs of distributive lattices, ICALP 2011.
  • C. Cheng and A. Lin, Stable Roommates Matchings, Mirror Posets, Median Graphs, and the Local/Global Median Phenomenon in Stable Matchings, SIAM Journal on Discrete Mathematics 25:1(2011) pp. 72-94.
  • C. Cheng, On Computing the Distinguishing and Distinguishing Chromatic Numbers of Interval Graphs and Other Results, Discrete Mathematics 309:16(2009) pp. 5169-5182.
  • C. Cheng, The Test Suite Generation Problem: Optimal Instances and Their Implications . Discrete Applied Mathematics, 155:15(2007) pp.1943-1957.

Community Involvement

  • GEMS (Girls in Engineering, Math and Science)
  • STEM (Science Technology Engineering and Mathematics)