Christine Cheng, Ph.D.
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. A 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.
- Ph.D., Johns Hopkins University, 1999
- M.S., Johns Hopkins University, 1996
- B.S., University of the Philippines, 1994
- Algorithm Design
- Graph Algorithms
- Combinatorial Optimization
- Graph Theory
- 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.
- GEMS (Girls in Engineering, Math and Science)
- STEM (Science Technology Engineering and Mathematics)