Christine Cheng's homepage |
|  |
|
I'm an Assistant 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 one, Madison Elle.
The Midwest Theory Day for Spring, 2009 will be held here at UWM on Saturday, April 25, 2009. If you're interested in CS Theory, come join us!
Contact Information
Department of Electrical Engineering and Computer Science
University of Wisconsin-Milwaukee
3200 N. Cramer Ave.
Milwaukee, WI 53211
Phone: 414.229.5170
Fax: 414.229.2769
E-mail: ccheng at uwm dot edu
Teaching
Research Interests
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.
Papers
Stable Matchings
- C. Cheng and A. Lin, Stable Roommates Matchings, Mirror Posets, Median Graphs, and the Local/Global Median Phenomenon in Stable Matchings, submitted.
- C. Cheng, Understanding the Generalized Median Stable Matchings, accepted to Algorithmica.
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, accepted to Discrete Mathematics.
- V. Arvind, C. Cheng, N. Devanur, On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach.
SIAM Journal of 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
Declustering Schemes
Others
- 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.
Book Chapter
- 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.
Last modified: Mon Apr 6 15:44:56 CDT 2009