Minghui Jiang Department of Computer Science Utah State University 4205 Old Main Hill Logan, UT 84322, USA @ mjiang    cc.usu.edu http://www.cs.usu.edu/~mjiang/  Phone: 1-435-797-0347    Fax: 1-435-797-3265 Office: Main 402G when in doubt...

About Me

Minghui Jiang is an Associate Professor of Computer Science at Utah State University. He received the B.S. degree in Physics from Peking University in 1997, the M.S. degree in Physics and the M.S. degree in Computer Science from Purdue University in 1999, and the Ph.D. degree in Computer Science from Montana State University in 2005. His research interests span many areas of theoretical computer science broadly connected to the design and analysis of algorithms, such as discrete and computational geometry, combinatorial optimization, and bioinformatics algorithms. His Erdős number is 2.

iTeach

• CS 2420 Data Structures and Algorithms   [ F08 S11 ]
• CS 5050 Advanced Algorithms   [ S06 F06 F07 S10 S11 S12 ]
• CS 5660 Bioinformatics I   [ S06 F09 F10 F11 ]
• CS 5670 Bioinformatics II   [ S07 S08 S09 S10 ]
• CS 6050 Computational Geometry   [ S07 S08 S09 S12 ]

A solution to Professor Layton and the Diabolical Box Puzzle 118, found by a C program using breadth-first search and hash table!

Java applet games Tetris NP-Ball.

Bioinformatics tools uShuffle RNA.

iResearch

-2005 2006 2007 2008 2009 2010 2011 2012

2012

• Guillaume Blin, Laurent Bulteau, Minghui Jiang, Pedro J. Tejada, and Stéphane Vialette. Hardness of longest common subsequence for sequences with bounded run-lengths. In Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM'12), to appear, July 3-5, 2012.
• Laurent Bulteau and Minghui Jiang. Inapproximability of (1,2)-exemplar distance. In Proceedings of the 2012 International Symposium on Bioinformatics Research and Applications (ISBRA'12), volume 7292 of Lecture Notes in Bioinformatics, pages 13-23, Springer, May 21-23, 2012. [ slides slides6 ]
• Minghui Jiang. On covering points with minimum turns. In Proceedings of the 6th International Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM'12), volume 7285 of Lecture Notes in Computer Science, pages 58-69, Springer, May 14-16, 2012. [ slides slides6 ]

• Minghui Jiang. Recognizing d-interval graphs and d-track interval graphs. Algorithmica, doi:10.1007/s00453-012-9651-5, online first April 24, 2012.
• Laurent Bulteau, Guillaume Fertin, Minghui Jiang, and Irena Rusu. Tractability and approximability of maximal strip recovery. Theoretical Computer Science, doi:10.1016/j.tcs.2012.04.034, accepted April 20, 2012.
• Minghui Jiang. Flipping triangles and rectangles. Journal of Combinatorial Optimization, doi:10.1007/s10878-012-9480-0, online first March 24, 2012.
• Adrian Dumitrescu and Minghui Jiang. On the largest empty axis-parallel box amidst n points. Algorithmica, doi:10.1007/s00453-012-9635-5, online first March 7, 2012. [ arxiv ]
• Minghui Jiang. Approximability of constrained LCS. Journal of Computer and System Sciences, 78:689-697, 2012.
• Adrian Dumitrescu and Minghui Jiang. Minimum-perimeter intersecting polygons. Algorithmica, 63:602-615, 2012.
• Minghui Jiang, Vincent Pilaud, and Pedro J. Tejada. On a dispersion problem in grid labeling. SIAM Journal on Discrete Mathematics, 26:39-51, 2012.
• Minghui Jiang and Yong Zhang. Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy. Theoretical Computer Science, doi:10.1016/j.tcs.2012.01.025, online first January 24, 2012. [ arxiv ]

• Minghui Jiang. Clique in 3-track interval graphs is APX-hard. Manuscript, 2012. [ arxiv preprint ]
• Adrian Dumitrescu and Minghui Jiang. Disjoint empty disks supported by a point set. Manuscript, 2012. [ arxiv ]

2011

• Minghui Jiang and Yong Zhang. Parameterized complexity in multiple-interval graphs: domination. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC'11), volume 7112 of Lecture Notes in Computer Science, pages 27-40, Springer, September 7-9, 2011. [ arxiv journal ]
• Adrian Dumitrescu, Minghui Jiang, and János Pach. Opaque sets. In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'11), volume 6845 of Lecture Notes in Computer Science, pages 194-205, Springer, August 17-19, 2011. [ slides slides6 arxiv ]
• Minghui Jiang and Yong Zhang. Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy. In Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON'11), volume 6842 of Lecture Notes in Computer Science, pages 62-73, Springer, August 14-16, 2011. [ slides slides6 arxiv journal ]
• Minghui Jiang. Flipping triangles and rectangles. In Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON'11), volume 6842 of Lecture Notes in Computer Science, pages 543-554, August 14-16, 2011. [ slides slides6 journal ]
• Adrian Dumitrescu and Minghui Jiang. Sweeping an oval to a vanishing point. In Proceedings of the XIV Spanish Meeting on Computational Geometry (EGC'11), volume 8 of Centre de Recerca Matemàtica Documents, pages 59-62, June 27-30, 2011. [ arxiv journal ]
• Laurent Bulteau, Guillaume Fertin, Minghui Jiang, and Irena Rusu. Tractability and approximability of maximal strip recovery. In Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM'11), volume 6661 of Lecture Notes in Computer Science, pages 336-349, Springer, June 27-29, 2011. [ journal ]

• Minghui Jiang. The zero exemplar distance problem. Journal of Computational Biology, 18:1077-1086, 2011. [ arxiv ]
• Minghui Jiang, Xiaojun Qi, and Pedro J. Tejada. A computational-geometry approach to digital image contour extraction. Transactions on Computational Science, XIII, volume 6750 of Lecture Notes in Computer Science, pages 13-43, 2011. [ Contour ]
• Adrian Dumitrescu and Minghui Jiang. Sweeping an oval to a vanishing point. Discrete Applied Mathematics, 159:1436-1442, 2011. [ arxiv ]
• Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth. New bounds on the average distance from the Fermat-Weber center of a planar convex body. Discrete Optimization, 8:417-427, 2011. [ arxiv ]
• Adrian Dumitrescu and Minghui Jiang. Piercing translates and homothets of a convex body. Algorithmica, 61:94-115, 2011.
• Adrian Dumitrescu and Minghui Jiang. Coloring translates and homothets of a convex body. Beiträge zur Algebra und Geometrie, doi:10.1007/s13366-011-0048-4, online first May 12, 2011. [ arxiv ]
• Adrian Dumitrescu and Minghui Jiang. Dispersion in disks. Theory of Computing Systems, doi:10.1007/s00224-011-9331-x, online first May 11, 2011. [ arxiv ]
• Minghui Jiang. Inapproximability of maximal strip recovery. Theoretical Computer Science, 412:3759-3774, 2011. [ arxiv ]
• Sergey Bereg, Minghui Jiang, Boting Yang, and Binhai Zhu. On the red/blue spanning tree problem. Theoretical Computer Science, 412:2459-2467, 2011.
• Adrian Dumitrescu and Minghui Jiang. Sweeping points. Algorithmica, 60:703-717, 2011.
• Adrian Dumitrescu and Minghui Jiang. Constrained k-center and movement to independence. Discrete Applied Mathematics, 159:859-865, 2011.
• Adrian Dumitrescu and Minghui Jiang. The forest hiding problem. Discrete & Computational Geometry, 45:529-552, 2011.
• Minghui Jiang. An inequality on the edge lengths of triangular meshes. Computational Geometry: Theory and Applications, 44:100-103, 2011.

2010

• Minghui Jiang. Approximability of constrained LCS. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC'10), volume 6507 of Lecture Notes in Computer Science, pages 180-191, Springer, December 15-17, 2010. [ slides slides6 ann-yeong-haseyo kamsa-hamnida journal ]
• Minghui Jiang. The zero exemplar distance problem. In Proceedings of the 8th Annual RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'10), volume 6398 of Lecture Notes in Bioinformatics, pages 74-82, Springer, October 9-11, 2010. [ slides slides6 arxiv journal ]
• Minghui Jiang. Recognizing d-interval graphs and d-track interval graphs. In Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW'10), volume 6213 of Lecture Notes in Computer Science, pages 160-171, Springer, August 11-13, 2010. [ slides slides6 journal ]
• Minghui Jiang. Inapproximability of maximal strip recovery: II. In Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW'10), volume 6213 of Lecture Notes in Computer Science, pages 53-64, Springer, August 11-13, 2010. [ slides slides6 arxiv journal ]
• Minghui Jiang, Vincent Pilaud, and Pedro J. Tejada. On a dispersion problem in grid labeling. In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG'10), pages 75-78, August 9-11, 2010. [ journal ]
• Adrian Dumitrescu and Minghui Jiang. Constrained k-center and movement to independence. In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG'10), pages 233-236, August 9-11, 2010. [ journal ]
• Minghui Jiang. On the parameterized complexity of some optimization problems related to multiple-interval graphs. In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM'10), volume 6129 of Lecture Notes in Computer Science, pages 125-137, Springer, June 21-23, 2010. [ slides slides6 journal ]
• Adrian Dumitrescu and Minghui Jiang. Minimum-perimeter intersecting polygons. In Proceedings of the 9th Latin American Symposium on Theoretical Informatics (LATIN'10), volume 6034 of Lecture Notes in Computer Science, pages 433-445, Springer, April 19-23, 2010. [ slides slides6 journal ]
• Adrian Dumitrescu and Minghui Jiang. Dispersion in unit disks. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'10), pages 299-310, March 4-6, 2010. [ journal ]
• Adrian Dumitrescu and Minghui Jiang. The forest hiding problem. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), pages 1566-1579, January 17-19, 2010. [ journal ]

• Minghui Jiang. On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411:4253-4262, 2010.
• Minghui Jiang, Pedro J. Tejada, Ramoni O. Lasisi, Shanhong Cheng, and D. Scott Fechser. K-partite RNA secondary structures. Journal of Computational Biology, 17:915-925, 2010. [ K-partite ]
• Minghui Jiang. Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7:323-332, 2010.
• Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang. Maximum area independent sets in disk intersection graphs. International Journal of Computational Geometry and Applications, 20:105-118, 2010.
• Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang. On covering problems of Rado. Algorithmica, 57:538-561, 2010.
• Adrian Dumitrescu and Minghui Jiang. Covering a disk by disks. Beiträge zur Algebra und Geometrie, 51:91-109, 2010.
• Adrian Dumitrescu and Minghui Jiang. Monochromatic simplices of any volume. Discrete Mathematics, 310:956-960, 2010.

2009

• Minghui Jiang. Inapproximability of maximal strip recovery. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), volume 5878 of Lecture Notes in Computer Science, pages 616-625, Springer, December 16-18, 2009. [ slides slides6 arxiv journal ]
• Minghui Jiang, Pedro J. Tejada, Ramoni O. Lasisi, Shanhong Cheng, and D. Scott Fechser. K-partite RNA secondary structures. In Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI'09), volume 5724 of Lecture Notes in Bioinformatics, pages 157-168, Springer, September 12-13, 2009. [ slides slides6 journal K-partite ]
• Adrian Dumitrescu and Minghui Jiang. Piercing translates and homothets of a convex body. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09), volume 5757 of Lecture Notes in Computer Science, pages 131-142, Springer, September 7-9, 2009. [ slides slides6 arxiv journal ]
• Adrian Dumitrescu and Minghui Jiang. On reconfiguration of disks in the plane and related problems. In Proceedings of the 11th Algorithms and Data Structures Symposium (WADS'09), volume 5664 of Lecture Notes in Computer Science, pages 254-265, Springer, August 21-23, 2009. [ slides slides6 ]
• Minghui Jiang. An inequality on the edge lengths of triangular meshes. In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG'09), pages 141-144, August 17-19, 2009. [ slides slides6 journal ]
• Pedro J. Tejada, Xiaojun Qi, and Minghui Jiang. Computational geometry of contour extraction. In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG'09), pages 25-28, August 17-19, 2009. [ Contour journal ]
• Sergey Bereg, Minghui Jiang, Boting Yang, and Binhai Zhu. On the red/blue spanning tree problem. In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC'09), volume 5532 of Lecture Notes in Computer Science, pages 118-127, Springer, May 18-22, 2009. [ journal ]

• Joel Gillespie, Martin Mayne, and Minghui Jiang. RNA folding on the 3D triangular lattice. BMC Bioinformatics, 10:#369, 2009. [ DeltaIS ]
• Zhixiang Chen, Bin Fu, Minghui Jiang, and Binhai Zhu. On recovering syntenic blocks from comparative maps. Journal of Combinatorial Optimization, 18:307-318, 2009.
• Minghui Jiang. A linear-time algorithm for Hamming distance with shifts. Theory of Computing Systems, 44:349-355, 2009.
• Sergey Bereg, Ovidiu Daescu, and Minghui Jiang. A PTAS for cutting out polygons with lines. Algorithmica, 53:157-171, 2009.

• Minghui Jiang and Pedro J. Tejada. Spreading grid cells. Manuscript, 2009. [ arxiv journal ]

2008

• Adrian Dumitrescu and Minghui Jiang. Sweeping points. In Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'08), volume 5171 of Lecture Notes in Computer Science, pages 63-76, Springer, August 25-27, 2008. [ slides slides6 journal ]
• Zhixiang Chen, Bin Fu, Minghui Jiang, and Binhai Zhu. On recovering syntenic blocks from comparative maps. In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08), volume 5165 of Lecture Notes in Computer Science, pages 319-327, Springer, August 21-24, 2008. [ journal ]
• Adrian Dumitrescu and Minghui Jiang. Monochromatic simplices of any volume. In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG'08), pages 71-74, August 13-15, 2008. [ journal ]
• Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang. On covering problems of Rado. In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT'08), volume 5124 of Lecture Notes in Computer Science, pages 294-305, Springer, July 2-4, 2008. [ slides slides6 journal ]
• Sergey Bereg, Minghui Jiang, Wencheng Wang, Boting Yang, and Binhai Zhu. Simplifying 3D polygonal chains under the discrete Fréchet distance. In Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN'08), volume 4957 of Lecture Notes in Computer Science, pages 630-641, Springer, April 7-11, 2008.

• Minghui Jiang, James Anderson, Joel Gillespie, and Martin Mayne. uShuffle: a useful tool for shuffling biological sequences while preserving the k-let counts. BMC Bioinformatics, 9:#192, 2008. [ uShuffle ]
• Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. Journal of Bioinformatics and Computational Biology, 6:51-64, 2008. [ applet ]
• Adrian Dumitrescu and Minghui Jiang. On a covering problem for equilateral triangles. Electronic Journal of Combinatorics, 15:#R37, 2008.
• Minghui Jiang. On the sum of distances along a circle. Discrete Mathematics, 308:2038-2045, 2008.

2007

• Minghui Jiang. A PTAS for the weighted 2-interval pattern problem over the preceding-and-crossing model. In Proceedings of the 1st Annual International Conference on Combinatorial Optimization and Applications (COCOA'07), volume 4616 of Lecture Notes in Computer Science, pages 378-387, Springer, August 12-15, 2007. [ slides slides6 journal ]
• Minghui Jiang and Vladimir Kulyukin. Connect-the-dots in a graph and Buffon's needle on a chessboard: two problems in assisted navigation. In Proceedings of the 10th Joint Conference on Information Sciences / the 10th International Conference on Computer Science and Informatics (JCIS/CSI'07), pages 713-719, World Scientific, July 18-24, 2007. [ slides slides6 ]
• Vladimir Kulyukin, Aliasgar Kutiyanawala, and Minghui Jiang. Surface-embedded passive RF exteroception: Kepler, Greed, and Buffon's needle. In Proceedings of the 4th International Conference on Ubiquitous Intelligence and Computing (UIC'07), volume 4611 of Lecture Notes in Computer Science, pages 33-42, Springer, July 11-13, 2007.
• Minghui Jiang, James Anderson, Joel Gillespie, and Martin Mayne. uShuffle: a useful tool for shuffling biological sequences while preserving the k-let counts. In Proceedings of the 2007 International Conference on Bioinformatics and Computational Biology (BIOCOMP'07), volume II, pages 605-613, CSREA Press, June 25-28, 2007. [ journal uShuffle ]
• Minghui Jiang. Improved approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. In Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM'07), volume 4508 of Lecture Notes in Computer Science, pages 399-410, Springer, June 6-8, 2007. [ slides slides6 journal ]
• Minghui Jiang, Martin Mayne, and Joel Gillespie. Delta: a toolset for the structural analysis of biological sequences on a 3D triangular lattice. In Proceedings of the 3rd International Symposium on Bioinformatics Research and Applications (ISBRA'07), volume 4463 of Lecture Notes in Bioinformatics, pages 518-529, Springer, May 7-10, 2007. [ journal Delta ]
• Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. In Proceedings of the 5th Asia Pacific Bioinformatics Conference (APBC'07), pages 131-141, Imperial College Press, January 14-17, 2007. [ journal applet ]

• Minghui Jiang. On finding a large number of 3D points with a small diameter. Discrete Applied Mathematics, 155:2355-2361, 2007.
• Minghui Jiang and Joel Gillespie. Engineering the divide-and-conquer closest pair algorithm. Journal of Computer Science and Technology, 22:532-540, 2007. [ program ]
• Minghui Jiang. A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem. Journal of Combinatorial Optimization, 13:217-221, 2007.

2006

• Chaitanya Gharpure, Vladimir Kulyukin, Minghui Jiang, and Aliasgar Kutiyanawala. Passive radio frequency exteroception in robot assisted shopping for the blind. In Proceedings of the 3rd International Conference on Ubiquitous Intelligence and Computing (UIC'06), volume 4159 of Lecture Notes in Computer Science, pages 51-60, Springer, September 3-6, 2006.
• Sergey Bereg, Ovidiu Daescu, and Minghui Jiang. A PTAS for cutting out polygons with lines. In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON'06), volume 4112 of Lecture Notes in Computer Science, pages 176-185, Springer, August 15-18, 2006. [ journal ]
• Minghui Jiang. Subsequence packing: complexity, approximation, and application. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM'06), volume 4041 of Lecture Notes in Computer Science, pages 314-323, Springer, June 20-22, 2006.

• Minghui Jiang. A new approximation algorithm for labeling points with circle pairs. Information Processing Letters, 99:125-129, 2006.
• Binhai Zhu and Minghui Jiang. A combinatorial theorem for labeling squares with points and its application. Journal of Combinatorial Optimization, 11:411-420, 2006.
• Minghui Jiang. Approximating minimum coloring and maximum independent set in dotted interval graphs. Information Processing Letters, 98:29-33, 2006.

2005 and before

• Minghui Jiang, Sergey Bereg, Zhongping Qin, and Binhai Zhu. New bounds on map labeling with circular labels. In Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC'04), volume 3341 of Lecture Notes in Computer Science, pages 606-617, Springer, December 22-24, 2004. [ applet ]
• Sergey Bereg, Minghui Jiang, and Binhai Zhu. Contour interpolation with bounded dihedral angles. In Proceedings of the 9th ACM Symposium on Solid Modeling and Applications (SM'04), pages 303-308, June 9-11, 2004.
• Minghui Jiang, Brendan Mumey, Zhongping Qin, Andrew Tomascak, and Binhai Zhu. Approximations for two decomposition-based geometric optimization problems. In Proceedings of the 2004 International Conference on Computational Science and its Applications (ICCSA'04), volume 3045 of Lecture Notes in Computer Science, pages 90-98, Springer, May 14-17, 2004.
• Nicholas J. Giordano, Minghui Jiang, and Stu Dietz. Experimental and computational studies of the piano. In Proceedings of the 17th International Congress on Acoustics, volume 4, September 2-7, 2001.
• Minghui Jiang and Nicholas J. Giordano. Sound production by a vibrating piano soundboard: Theory. In Program Abstracts of the 138th Meeting of the Acoustical Society of America, volume 106 of Journal of the Acoustical Society of America, issue 4, page 2141, November 1-5, 1999.

• Minghui Jiang and Binhai Zhu. Protein folding on the hexagonal lattice in the HP model. Journal of Bioinformatics and Computational Biology, 3:19-34, 2005. [ applet ]
• Minghui Jiang. UPS-k: a set partitioning problem with applications in UPS pickup-delivery system. Information Processing Letters, 93:173-175, 2005.
• Nicholas J. Giordano and Minghui Jiang. Physical modeling of the piano. EURASIP Journal on Applied Signal Processing (now EURASIP Journal on Advances in Signal Processing), 2004:926-933, 2004.
• Minghui Jiang, Jianbo Qian, Zhongping Qin, Binhai Zhu, and Robert Cimikowski. A simple factor-3 approximation for labeling points with circles. Information Processing Letters, 87:101-105, 2003.

editorial board

• Journal of Discrete Mathematics

Tell me, what else should I have done?
Doesn't everything die at last, and too soon?
Tell me, what is it you plan to do
with your one wild and precious life?