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 picture of our little ones, Madison and Nolan.
Midwest Theory Day for Spring, 2009 was held here at UWM.
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. The specifics, however, are continually changing! They typically fall under one of the following categories: Algorithm Design, Combinatorial Optimization, Combinatorics, and Graph Theory.
- 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.
- 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, 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, 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.