## 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.

University of Wisconsin-Milwaukee

3200 N. Cramer Ave.

Milwaukee, WI 53211

Spring 2014 | |

CS 317 | Discrete Information Structures |

CS 704 | Analysis of Algorithms |

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.

- 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 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.

- 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.

- C. Cheng, The Test Suite Generation Problem: Optimal Instances and Their Implications . Discrete Applied Mathematics, 155:15(2007) pp.1943-1957.
- C. Cheng, A. Dumitrescu, P. Schroeder, Generating Small Combinatorial Test Suites to Cover Input-Output Relationships. Proceedings of 3rd Quality Software International Conference (QSIC '03) (2003) pp. 76-82. The following revised version contains corrections to the proceedings paper.

- C.-M Chen and C. Cheng, From Discrepancy to Declustering:Near-optimal Multidimensional Declustering Strategies for Range Queries. Journal of the ACM, 51:1 (2004) pp.46-73. A preliminary version appeared in the Proceedings of Principles of Database Systems, (PODS '02) (2002) pp.29-38. Awarded "PODS 2002 Best Newcomer Paper".
- C.-M. Chen, C. Cheng, Replication and Retrieval Strategies of Multidimensional Data on Parallel Disks. Proceedings of the ACM Conference on Information and Knowledge Management (CIKM '03), (2003) pp. 32-39.

- 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.

- 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.