Christine Cheng's homepage
I'm an Associate Professor at the Computer Science Department of the University of Wisconsin-Milwaukee . Prior to coming here in 2002, I was an Industrial Postdoctoral Associate at the Institute for Mathematics and its Applications (IMA), collaborating with research scientists at Telcordia Technologies. I received my Ph.D. from the Mathematical Sciences Department at Johns Hopkins University. My thesis advisor was Lenore Cowen.
Here is a photo of our kids, Madison and Nolan.
Department of Electrical Engineering and Computer Science
University of Wisconsin-Milwaukee
3200 N. Cramer Ave.
Milwaukee, WI 53211
E-mail: ccheng at uwm dot edu
The UWM Computer Science Department is a member of BRAID Building, Recruiting and Inclusion for Diversity. Through this initiative, we have sent some of our female undergraduate and graduate students to the Grace Hopper Conference .
We also started a Girls Who Code Club at UWM. Check out our video here.
My general interests lie at the intersection of computer science and discrete mathematics. They typically fall under one of the following categories: Algorithm Design, Combinatorial Optimization, Combinatorics, and Graph Theory.
- C. Cheng, K. L. Collins, A. Trenk, Split Graphs and Nordhaus-Gaddum Graphs, Discrete Mathematics 339 (2016), pp. 2345-2356
- C. Cheng, A. McConvey, D. Onderko, N. Shar, C. Tomlinson, Beyond knights and knaves, WG 2013.
- C. Cheng, A Poset-based Approach to Embedding Median Graphs in Hypercubes and Lattices, Order 29 (2012), pp. 147--163.
- C. Cheng and I. Suzuki, Weak Sense of Direction Labelings and Graph Embeddings,
Discrete Applied Mathematics 159 (2011), pp. 303-310.
- C. Cheng, E. McDermid, I. Suzuki, Planarization and acyclic colorings of subcubic claw-free graphs, WG 2011.
I gave an invited talk on Fair Stable Matchings at MATCH-UP 2015 which summarizes most of my work on the topic.
- C. Cheng On the Stable Matchings that can be Reached When the Agents Go Marching in One by One , accepted to SIAM Journal on Discrete Mathematics, 2016.
- C. Cheng, E. McDermid, I. Suzuki, Eccentricity, Center and Radius Computations on the Cover Graphs of Distributive Lattices with Applications to Stable Matchings , Discrete Applied Mathematics 205 (2016) pp. 27-34. A preliminary version of the paper is The center stable matchings and the centers of cover graphs of distributive lattices, ICALP 2011.
- 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 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, Understanding the Generalized Median Stable Matchings, Algorithmica 58:1(2010) pp. 34-51.
A preliminary version of this is The Generalized Median Stable Matchings: finding them is not that easy which appeared in the
Proceedings of the 8th Latin American Theoretical Informatics (LATIN '08) (2008), Lecture Notes in Computer Science Vol. 4957, pp. 568-579.
- C. Cheng, E. McDermid, I. Suzuki, A Unified Approach to Finding Good Stable Matchings in the Hospitals/Residents Setting.
Theoretical Computer Science 400:1-3(2008) pp.84-99.
- E. McDermid, C. Cheng, I. Suzuki, Hardness Results on the Man-Exchange Stable Marriage Problem with Short Preference Lists.
Information Processing Letters 101:1(2007) pp. 13-19.
Distinguishing Numbers of Graphs
- C. Cheng, On Computing the Distinguishing and Distinguishing Chromatic Numbers of Interval Graphs and Other Results, Discrete Mathematics 309:16(2009) pp. 5169-5182.
- V. Arvind, C. Cheng, N. Devanur, On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach.
SIAM Journal on Discrete Mathematics 22:4(2008) pp.1297-1324.
- C. Cheng, On Computing the Distinguishing Numbers of Trees and Forests.
Electronic Journal of Combinatorics 13:1(2006) R11.
- C. Cheng and L. J. Cowen, On Local Distinguishing Numbers of Cycles.
Discrete Mathematics, 196:1-3(1999) pp.97-108.
- C. Cheng, Local Distinguishing Numbers of Trees .
Congressus Numerantium, 133(1998) pp.21-30.
Generating Test Suites/Covering Arrays
- P. Haddawy, C. Cheng, N. Rujikeadkumjorn, K. Dhananaiyapergse, Balanced Matching of Buyers and Sellers in E-Marketplaces: The Barter Trade Exchange Model .
Electronic Commerce Research and Applications 4:4(2005) pp. 299-314. A preliminary version of the paper appeared in the Proceedings of the 6th International Conference on Electronic Commerce (ICEC '04), (2004).
- C. Cheng, Improved Approximation Algorithms for the Demand Routing and Slotting Problem with Unit Demands on Rings.
SIAM Journal of Discrete Mathematics 17:3(2004) pp. 384-402. A preliminary version appeared in the Proceedings of the 2nd Approximation Algorithms for Combinatorial Optimization (APPROX '99) (1999) pp.209-220.
- C. Cheng, H. Lemberg, S. Philip, E. van den Berg, T. Zhang,
SLALoM: A Scalable Location Management Scheme for Large Mobile Ad-hoc Networks.
Proceedings of Wireless Communications and Networking Conference (WCNC '02), (2002).
- C. Cheng, C.A. Duncan, M.T. Goodrich, K. Kobourov, Drawing Planar Graphs with Circular Arcs .
Discrete and Computational Geometry, 25(2001) pp.405-418. A preliminary version appeared in the Proceedings of the 7th Symposium on Graph Drawing (GD '99) (1999) pp. 186-196.
Last modified: Wed Jul 7 15:06:42 CDT 2010
- C. Cheng, R. Jain and E. van den Berg, Location Prediction Algorithms for Mobile Wireless Systems.
in Wireless Internet Handbook: Technologies, Standards and Applications, M. Ilyas and B. Furht (eds.) CRC Press, 2003, pp. 245-264.