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
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, submitted.
- C. Cheng, A. McConvey, D. Onderko, N. Shar, C. Tomlinson, Beyond knights and knaves, WG 2013.
- C. Cheng, E. McDermid, I. Suzuki, Planarization and acyclic colorings of subcubic claw-free graphs, WG 2011.
I recently 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 , submitted.
- C. Cheng, E. McDermid, I. Suzuki, Eccentricity, Center and Radius Computations on the Cover Graphs of Distributive Lattices with Applications to Stable Matchings , accepted to Discrete Applied Mathematics, November 2015. 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.