th access
Department of
Computing Science
 University of Alberta
Guohui Lin's Homepage | Calendar

[ Conference Proceedings Publications | Edited Works | Others ]

This list includes my fully refereed journal publications organized in chronological order.
Preliminary versions and extended abstracts previously appearing in conference proceedings are listed under their respective journal versions.

2010 2011 2012  2013
2009 2008 2007 2006 2005 2004 2003 2002 2001 2000
1997 1998 1999

You may want to check my lists of publications through DBLP, MathSciNet, and PubMed.

Copyright Notice. The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder(s).
  • Authors in bold are/were HQP at the University of Alberta.
  • 32 refereed conference proceedings publications are associated with 26 of the following 75 journal articles, respectively;
  • Co-first authors by †, correspondence authors by *, when not obvious.

In press:

  1. Y. Shi*, M. Hasan, Z. Cai, ——, and D. Schuurmans.
    Linear coherent bi-clustering via beam searching and sample set clustering.
    Discrete Mathematics, Algorithms and Applications. (SI for COCOA 2010).
    Accepted on December 31, 2011.
    1. Y. Shi, M. Hasan, Z. Cai, ——, and D. Schuurmans.
      Linear coherent bi-cluster discovery via beam detection and sample set clustering.
      In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010). LNCS 6509, Pages 85-103.
    2. Y. Shi, Z. Cai, ——, and D. Schuurmans.
      Linear coherent bi-cluster discovery via line detection and sample majority voting.
      In Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2009). LNCS 5573, Pages 73-84.
  2. ——*, R. Goebel, Z. Li, and L. Wang.
    An improved approximation algorithm for the complementary maximum strip recovery problem.
    Journal of Computer and System Sciences.
    Accepted on October 21, 2011.
    Abstract: Given two genomic maps G1 and G2 each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G1 and G2 such that the resultant subsequences, denoted as G1* and G2*, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7⁄3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme.
    (An extended abstract appears in FAW-AAIM 2011, LNCS 6681, pages 46-57.)
    1. Z. Li, R. Goebel, L. Wang, and ——.
      An improved approximation algorithm for the complementary maximum strip recovery problem.
      In Proceedings of the Joint Conference of the Fifth International Frontiers of Algorithmics Workshop and the Seventh International Conference on Algorithmic Aspects of Information and Management (FAW-AIMM 2011). LNCS 6681, Pages 46-57.

  3. H. Jiang, Z. Li, ——, L. Wang, and B. Zhu.
    Exact and approximation algorithms for the complementary maximum strip recovery problem.
    Journal of Combinatorial Optimization.
    Accepted on November 3, 2010.

2012:

  1. Y. Cheng and ——.
    Solving haplotype inference problem with non-genotyped founders via integer linear programming.
    Journal of Combinatorial Optimization. 23(1)(2012), 50-60.

2011:

  1. W. Ding*, ——, and G. Xue.
    Diameter-constrained Steiner trees.
    Discrete Mathematics, Algorithms and Applications. 3(4)(2011), 491-502.
    (An extended abstract appears in COCOA 2010, LNCS 6509, pages 243-253.)
    1. W. Ding, ——, and G. Xue.
      Diameter-constrained Steiner tree.
      In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010). LNCS 6509, Pages 243-253.

  2. ——.
    On the Bandpass problem.
    Journal of Combinatorial Optimization. 22(1)(2011), 71-77.
  3. Z.-Z. Chen*, ——, and L. Wang.
    An approximation algorithm for the minimum co-path set problem.
    Algorithmica. 60(4)(2011), 969-986.
  4. Z. Cai, Y. Duan, Y. Li, ——, M. Ozden, and X. Wan.
    IPMiner: a progenitor gene identifier for influenza A virus.
    Influenza and Other Respiratory Viruses. 5(S1; SI for Options for the Control of Influenza VII)(2011), 413-415.

  5. Z. Li and ——.
    The three column Bandpass problem is solvable in linear time.
    Theoretical Computer Science. 412(4-5)(2011), 281-299.
  6. Z. Cai, R. Goebel, and ——.
    Size-constrained tree partitioning: approximating the multicast k-tree routing problem.
    Theoretical Computer Science. 412(3; SI for COCOA'09)(2011), 240-245.
    Abstract: In the multicast k-tree routing problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting.s Several approximation algorithms, with increasing performance, have been proposed in the last several years; the most recent ones rely heavily on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line.s The algorithm has a worst-case performance ratio of 5ρ⁄4 + 3⁄2, where ρ denotes the best approximation ratio for the Steiner minimum tree problem. The proofs of the technical routing lemmas also provide some insights into why such a performance ratio could be the best possible that one can get using this tree partitioning technique.
    1. Z. Cai, R. Goebel, and ——.
      Size-constrained tree partitioning: a story on approximation algorithm design for the multicast k-tree routing problem.
      In Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09). LNCS 5573, Pages 363-374.

2010:


  1. J. Zhou, J. Sander*, Z. Cai, L. Wang, and ——*.
    Finding the nearest neighbors in biological databases using less distance computations.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 7(4)(2010), 669-680.
    Abstract: Modern biological applications usually involve the similarity comparison between two objects, which is often computationally very expensive, such as whole genome pairwise alignment and protein 3D structure alignment. Nevertheless, being able to quickly identify the closest neighboring objects from very large databases for a newly obtained sequence or structure can provide timely hints to its functions and more. This paper presents a substantial speedup technique for the well-studied k-nearest neighbor (k-nn) search, based on novel concepts of virtual pivots and partial pivots, such that a significant number of the expensive distance computations can be avoided. The new method is able to dynamically locate virtual pivots, according to the query, with increasing pruning ability. Using the same or less amount of database preprocessing effort, the new method outperformed the second best method by using no more than 40 percent distance computations per query, on a database of 10,000 gene sequences, compared to several best known k-nn search methods including M-Tree, OMNI, SA-Tree, and LAESA. We demonstrated the use of this method on two biological sequence data sets, one of which is for HIV-1 viral strain computational genotyping.
  2. [Web Server]
    M. Berjanskii, J. Liang, J. Zhou, P. Tang, P. Stothard, Y. Zhu, J. Cruz, C. Macdonell, ——, P. Lu, and D. S. Wishart.
    PROSESS: a protein structure evaluation suite and server. Open Access
    Nucleic Acids Research. 38(Web Server issue)(2010): W633-W640.

  3. W. S. Kennedy, H. Kong, ——*, and G. Yan.
    Linear time construction of 5-phylogenetic roots for tree chordal graphs.
    Journal of Combinatorial Optimization. 19(1)(2010), 94-106.

2009:


  1. Y. Cheng*, D.-Z. Du, K.-I. Ko, and ——.
    On the parameterized complexity of pooling design.
    Journal of Computational Biology. 16(11)(2009), 1529-1537.
  2. Z. Cai, Z.-Z. Chen, and ——.
    A 3.4713-approximation algorithm for the capacitated multicast tree routing problem.
    Theoretical Computer Science. 410(52)(2009), 5415-5424.

  3. J. Zhang, D. Xu, W. Gao, ——*, and S. He*.
    Isotope pattern vector based MS/MS data calibration for improving peptide and protein identification.
    Rapid Communications in Mass Spectrometry. 23(21)(2009), 3448-3456.
    Abstract: Tandem mass spectra contain noisy peaks which make peak picking for peptide identification difficult. Moreover, all spectral peaks can be shifted due to systematic measurement errors. In this paper, a novel use of an isotope pattern vector (IPV) is proposed for denoising and systematic measurement error prediction. By matching the experimental IPVs with the theoretical IPVs of candidate fragment ions, true ionic peaks can be identified. Furthermore, these identified experimental IPVs and their corresponding theoretical IPVs are used in an optimization process to predict the systematic measurement error associated with the target spectrum. In return, the subsequent spectral data calibration based on the predicted systematic measurement error enhances the data quality. We show that such an integrated denoising and calibration process leads to significantly improved peptide and protein identification. Different from the commonly employed chemical calibration methods, our IPV-based method is a purely computational method for individual spectra analysis and globally optimizes the use of spectral data.
  4. [Web Server]
    M. Berjanskii, P. Tang, J. Liang, J. A. Cruz, J. Zhou, Y. Zhu, E. Bassett, C. MacDonell, P. Lu, ——, and D. S. Wishart.
    GeNMR: a web server for rapid NMR-based protein structure determination. Open Access
    Nucleic Acids Research. 37(Web Server issue)(2009): W670-W677.

  5. Y. Cheng, H. Sabaa, Z. Cai, R. Goebel, and ——.
    Efficient haplotype inference algorithms in one whole genome scan for pedigree data with non-genotyped founders.
    Acta Mathematicae Applicatae Sinica (English Series). 25(3)(2009), 477-488.
    (SI dedicated to the 30th Anniversary of the Institute of Applied Mathematics within the Chinese Academy of Sciences.)
  6. [Supplementary Materials]

  7. G. N. Lin, Z. Cai, ——, S. Chakraborty, and D. Xu.
    ComPhy: prokaryotic composite distance phylogenies inferred from whole-genome gene sets.Open Access
    BMC Bioinformatics. 10(Suppl 1: SI for APBC'09)(2009), S5 (January 30, 2009).
    1. Presented at The Seventh Asia-Pacific Bioinformatics Conference (APBC'09).

  8. Y. Cheng*, D.-Z. Du, and ——.
    On the upper bounds of the minimum number of rows of disjunct matrices.
    Optimization Letters. 3(2)(2009), 297-302.

2008:


  1. M. E. J. Amaral*, J. R. Grant, P. K. Riggs, N. B. Stafuzza, E. A. R. Filho, T. Goldammer, R. Weikard, R. M. Brunner, K. J. Kochan, A. J. Greco, J. Jeong, Z. Cai, ——, A. Prasad, S. Kumar, G. P. Saradhi, B. Mathew, M. A. Kumar, M. N. Miziara, P. Mariani, A. R. Caetano, S. R. Galvão, M. S. Tantia, R. K. Vijh, B. Mishra, S. T. B. Kumar, V. A. Pelai, A. M. Santana, L. C. Fornitano, B. C. Jones, H. Tonhati, S. Moore, P. Stothard, and J. E. Womack.
    A first generation whole genome RH map of the river buffalo with comparison to domestic cattle.Open Access
    BMC Genomics. 9(2008), 631 (December 24, 2008).

  2. X.-F. Wan*, M. Ozden, and ——.
    Ubiquitous reassortments in influenza A viruses.
    Journal of Bioinformatics and Computational Biology. 6(5)(2008), 981-999.
  3. [Web Server]
    D. S. Wishart*, D. Arndt, M. Berjanskii, P. Tang, J. Zhou, and ——.
    CS23D: a web server for rapid protein structure generation using NMR chemical shifts and sequence data. Open Access
    Nucleic Acids Research. 36(Web Server Issue)(2008), W496-W502.
    (A poster by Wishart, Arndt, Berjanskii, Tang, Zhou, Shi, and Lin, presented in PrP Canada'08.)

  4. ——*, Z. Cai, J. Wu, X.-F. Wan, L. Xu, and R. Goebel.
    Identifying a few foot-and-mouth disease virus signature nucleotide strings for computational genotyping.Open Access
    BMC Bioinformatics. 9(2008): 279 (13Jun2008).
    (A preliminary version on string selection, by Wu and Lin, appears in IEEE CIBCB'05, pages 105-112.)
    1. X. Wu and ——.
      Selected string representation for whole genomes.
      In Proceedings of 2005 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (IEEE CIBCB'05). Pages 105-112.
  5. [Web Server]
    Y. Shi, J. Zhou, D. Arndt, D. S. Wishart*, and ——*.
    Protein contact order prediction from primary sequences. Open Access
    BMC Bioinformatics. 9(2008): 255(30May2008).
    (A poster by Zhou, Shi, Lin, and Wishart, presented in CPI'07.)
  7. [Web Server]
    D. S. Wishart*, D. Arndt, M. Berjanskii, A. C. Guo, Y. Shi, S. Shrivastava, J. Zhou, Y. Zhu, and ——.
    PPT-DB: the protein property prediction and testing database. Open Access
    Nucleic Acids Research. 36(Database Issue)(2008), D222-D229.

2007:

  1. [Supplementary Materials] (A preliminary version on HIV-1 pure subtyping, by Wu, Goebel, Wan, and Lin, appears in LSS CSB'06, pages 179-190. )
    1. X. Wu, R. Goebel, X.-F. Wan, and ——.
      Whole genome composition distance for HIV-1 genotyping.
      In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 179-190.
  2. [Supplementary Materials]
    X. Wan and ——.
    CISA: combined NMR resonance connectivity information determination and sequential assignment.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 4(3)(2007), 336-348.
  3. [Supplementary Materials]
    X. Wan and ——.
    GASA: a graph-based automated NMR backbone resonance sequential assignment program.
    Journal of Bioinformatics and Computational Biology. 5(2A)(2007), 313-333.
    (SI for LSS CSB'06: a preliminary version, by the same authors, appears in LSS CSB'06, pages 55-66. )
    1. X. Wan and ——.
      A graph-based automated NMR backbone resonance sequential assignment.
      In Proceedings of the 2006 LSS Computational Systems Bioinformatics Conference (LSS CSB'06). Pages 55-66.
  4. [Supplementary Materials] (Preliminary versions, by Cai, Goebel, Salavatipour, Shi, Xu, and Lin, appears in APBC'07, pages 81-90;
    and by Cai, Xu, Shi, Salavatipour, Goebel, and Lin, appears in IEEE BIBE'06, pages 235-242.)
    1. Z. Cai, R. Goebel, M. Salavatipour, Y. Shi, L. Xu, and ——.
      Selecting genes with dissimilar discrimination strength for sample class prediction.
      In Proceedings of the Fifth Asia-Pacific Bioinformatics Conference (APBC'07). Pages 81-90.
    2. Z. Cai, L. Xu, Y. Shi, M. Salavatipour, R. Goebel, and ——.
      Using gene clustering to identify discriminatory genes with higher classification accuracy.
      In Proceedings of IEEE The 6th Symposium on Bioinformatics and Bioengineering (IEEE BIBE'06). Pages 235-242.

  5. X.-F. Wan†*, X. Wu†, ——, S. B. Holton, R. A. Desmone, C.-R. Shyu, Y. Guan, and M. Emch.
    Computational identification of reassortments in avian influenza viruses.
    Avian Diseases. 51(s1)(2007), 434-439.
    (SI for ISAI'06: an abstract, by Wu, Holton, Shyu, Lin, and Wan, presented as a poster in ISAI'06, 2006.)
  6. [Supplementary Materials]
    G. Wu, J. You, and ——.
    Quartet based phylogeny reconstruction with answer set programming.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics. 4(1)(2007), 139-152.
    (Preliminary versions of several parts, by Wu, You, and Lin, appears in LPNMR'05, LNCS/LNAI 3663, pages 369-373;
    and by Wu, Lin, You, and Wu, appears in APBC'05, pages 329-338;
    and by Wu, Lin, and You, appears in IEEE ICTAI'04, pages 612-619.)
    1. G. Wu, J. You, and ——.
      Application of Smodels in quartet based phylogeny construction.
      In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05). LNCS/LNAI 3662, Pages 369-373.
    2. G. Wu, ——, J. You, and X. Wu.
      Faster solution to the maximum quartet consistency problem with constrained programming.
      In Proceedings of the 3rd Asia-Pacific Bioinformatics Conference (APBC'05). Pages 329-338.
    3. G. Wu, ——, and J. You.
      Quartet based phylogeny reconstruction with answer set programming.
      In Proceedings of The 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'04). Pages 612-619.

  7. J. Zhou, J. Sander, and ——.
    Efficient composite pattern finding from monad patterns.
    International Journal on Bioinformatics Research and Applications. 3(1)(2007), 86-99.

2006:

  1. [Supplementary Materials]
    Z. Cai, M. Heydari, and ——.
    Iterated local least squares imputation for microarray missing values.
    Journal of Bioinformatics and Computational Biology. 4(5)(2006), 935-957.
    (A preliminary version, by the same authors, appears in APBC'06, pages 159-168.)
    1. Z. Cai, M. Heydari, and ——.
      Microarray missing value imputation by iterated local least squares.
      In Proceedings of the Fourth Asia-Pacific Bioinformatics Conference (APBC'06). Pages 159-168.

  2. X.-F. Wan, ——, and D. Xu.
    Rnall: an efficient algorithm for predicting RNA local secondary structural landscape in genomes.
    Journal of Bioinformatics and Computational Biology. 4(5)(2006), 1015-1031.
  3. W. Kennedy, ——, and G. Y. Yan.
    Strictly chordal graphs are leaf powers.
    Journal of Discrete Algorithms. 4(4)(2006), 511-525.
  4. G. Wu, J. You, and ——.
    A polynomial time algorithm for the minimum quartet inconsistency problem with O(n) quartet errors.
    Information Processing Letters. 100(4)(2006), 167-171.
    (An extended abstract, by the same authors, appears in Posters in IEEE CSB'05, pages 55-56.)

  5. X. Wu, X.-F. Wan, G. Wu, D. Xu, and ——.
    Phylogenetic analysis using complete signature information of whole genomes and clustered Neighbor-Joining method.
    International Journal on Bioinformatics Research and Applications. 2(3)(2006), 219-248.
  6. K. Yang†, Z. Cai†, J. Li, and ——*.
    A stable gene selection in microarray data analysis. Open Access
    BMC Bioinformatics. 7(2006): 228.
    (A preliminary version, by Yang, Li, Cai, and Lin, appears in IEEE BIBE'05, pages 3-10.)
    1. K. Yang, Z. Cai, J. Li and ——.
      A model-free and stable gene selection in microarray data analysis.
      In Proceedings of IEEE The 5th Symposium on Bioinformatics and Bioengineering (IEEE BIBE'05). Pages 3-10.

  7. ——*, X. Wan, T. Tegos, and Y. Li.
    Statistical evaluation of NMR backbone resonance assignment.
    International Journal of Bioinformatics Research and Applications. 2(2)(2006), 147-160.
  8. ——*, Z. Cai, and D. Lin.
    Path covering on trees with its applications in machine translation.
    Information Processing Letters. 97(2)(2006), 73-81.

2005:


  1. T. Tegos, Z.-Z. Chen, and ——.
    Heuristic search in constrained bipartite matching with applications to protein NMR backbone resonance assignment.
    Journal of Bioinformatics and Computational Biology. 3(6)(2005), 1331-1350.
  2. ——.
    An improved approximation algorithm for multicast k-tree routing.
    Journal of Combinatorial Optimization. 9(4)(2005), 349-356.
  3. Z. Cai, M. Heydari, and ——.
    Clustering binary oligonucleotide fingerprint vectors for DNA clone classification analysis.
    Journal of Combinatorial Optimization. 9(2)(2005), 199-211.

  4. Z.-Z. Chen, ——, R. Rizzi, J.-J. Wen, D. Xu, Y. Xu, and T. Jiang.
    More reliable protein NMR peak assignment via improved 2-interval scheduling.
    Journal of Computational Biology. 12(2)(2005), 129-146.
    (An extended abstract, by Chen, Jiang, Lin, Rizzi, Wen, Xu, and Xu, appears in ESA'03, LNCS 2832, pages 580-592.)
    1. Z.-Z. Chen, T. Jiang, ——, R. Rizzi, J. J. Wen, D. Xu, and Y. Xu.
      More reliable protein NMR peak assignment via improved 2-interval scheduling.
      In Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03). LNCS 2832, Pages 580-592.

2004:


  1. X. Wan, T. Tegos, and ——.
    Histogram-based scoring schemes for protein NMR resonance assignment.
    Journal of Bioinformatics and Computational Biology. 2(4)(2004), 747-764.
    (A preliminary version of one part, by Wan, Xu, Slupsky, and Lin, appears in IEEE CSB'03, pages 197-208. )
    1. X. Wan, D. Xu, C. M. Slupsky, and ——.
      Automated protein NMR resonance assignments.
      In Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference (CSB'03). Pages 197--208.
  2. Z.-Z. Chen, Y. Gao, ——*, R. Niewiadomski, Y. Wang, and J. Wu.
    A space-efficient algorithm for sequence alignment with inversions and reversals.
    Theoretical Computer Science. 325(3)(2004), 361-372.
    (SI for COCOON'03: A preliminary version, by Gao, Wu, Niewiadomski, Wang, Chen, and Lin, appears in COCOON'03, LNCS 2697, pages 57-67.)
    1. Y. Gao, J. Wu, R. Niewiadomski, Y. Wang, Z.-Z. Chen, and ——.
      A space efficient algorithm for sequence alignment with inversions.
      In Proceedings of the Ninth International Computing and Combinatorics Conference (COCOON'03). LNCS 2697, Pages 57-67.
  3. ——* and T. Jiang.
    A further improved approximation algorithm for breakpoint graph decomposition.
    Journal of Combinatorial Optimization. 8(2)(2004), 183-194.
  4. T. Jiang, ——*, B. Ma, and K. Zhang.
    The longest common subsequence problem for arc-annotated sequences.
    Journal of Discrete Algorithms. 2(2)(2004), 257-270.
    (SI for CPM'00: An extended abstract, by the same authors, appears in CPM'00, LNCS 1848, pages 154-165.)
    1. T. Jiang, ——, B. Ma, and K. Zhang.
      The longest common subsequence problem for arc-annotated sequences.
      In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00). LNCS 1848, Pages 154-165.

2003:


  1. ——, D. Xu, Z.-Z. Chen, T. Jiang, J.-J. Wen, and Y. Xu.
    Computational assignment of protein backbone NMR peaks by efficient bounding and filtering.
    Journal of Bioinformatics and Computational Biology. 1(2)(2003), 387-410.
    (SI for IEEE CSB'02: A preliminary version of one part, by Lin, Xu, Chen, Jiang, Wen, and Xu, appears in IEEE CSB'02, pages 165-174. )
    1. ——, D. Xu, Z.-Z. Chen, T. Jiang, and Y. Xu.
      An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks.
      In Proceedings of the IEEE Computer Society Bioinformatics Conference 2002 (CSB'02). Pages 165-174.
  2. Z.-Z. Chen, T. Jiang*, and ——.
    Computing phylogenetic roots with bounded degrees and errors.
    SIAM Journal on Computing. 32(2003), 864-879.
    (An extended abstract, by the same authors, appears in WADS'01, LNCS 2125, pages 377-388.)
    1. Z.-Z. Chen, T. Jiang, and ——.
      Computing phylogenetic roots with bounded degrees and errors.
      In Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS'01). LNCS 2125, Pages 377-388.
  3. E. Bach, J. Boyar, L. Epstein, L. M. Favrholdt, T. Jiang, K. S. Larsen, ——, and R. van Stee.
    Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem.
    Journal of Scheduling. 6(2)(2003), 131-147.
    (An extended abstract, by Bach, Boyar, Jiang, Larsen, and Lin, appears in COCOON'00, LNCS 1858, pages 221-231.)
    1. E. Bach, J. Boyar, T. Jiang, K. S. Larsen, and ——.
      Better bounds on the accommodating ratio for seat reservation problem.
      In Proceedings of the 6th Annual International Computing and Combinatorics Conference (COCOON'00). LNCS 1858, Pages 221-231.
  4. Z.-Z. Chen, T. Jiang, ——, J.-J. Wen, D. Xu, J. Xu, and Y. Xu.
    Approximation algorithms for NMR spectral peak assignment.
    Theoretical Computer Science. 299(1-3)(2003), 211-229.
    (A preliminary version, by Chen, Jiang, Lin, Wen, Xu, and Xu, appears in WABI'02, LNCS 2452, pages 82-96.)
    1. Z.-Z. Chen, T. Jiang, ——, J. J. Wen, D. Xu, and Y. Xu.
      Better approximation algorithms for NMR spectral peak assignment.
      In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI'02). LNCS 2452, Pages 82-96.

2002:

  1. ——, Z.-Z. Chen, T. Jiang, and J.-J. Wen.
    The longest common subsequence problem for sequences with nested arc annotations.
    Journal of Computer and System Sciences. 65(3)(2002), 465-480.
    (An extended abstract, by the same authors, appears in ICALP'01, LNCS 2076, pages 444-455.)
    1. ——, Z.-Z. Chen, T. Jiang, and J.-J. Wen.
      The longest common subsequence problem for sequences with nested arc annotations.
      In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP'01). LNCS 2076, Pages 444-455.
  2. D. Jaitly, P.E. Kearney, ——, and B. Ma.
    Methods for reconstructing the history of tandem repeats and their application to the human genome.
    Journal of Computer and System Sciences. 65(3)(2002), 494-507.
  3. [citations] —— and G.L. Xue.
    On the terminal Steiner tree problem.
    Information Processing Letters. 84(2)(2002), 103-107.
  4. [Supplementary Materials]
    T. Jiang, ——, B. Ma, and K. Zhang.
    A general edit distance between RNA structures.
    Journal of Computational Biology. 9(2)(2002), 371-388.
    (An extended abstract, by Lin, Ma, and Zhang, appears in ACM RECOMB'01, pages 211-220.)
    1. ——, B. Ma, and K. Zhang.
      Edit distance between two RNA structures.
      In Proceedings of the 5th ACM Annual International Conference on Computational Molecular Biology (RECOMB'01). Pages 200-209.
  5. S. P. Chen, Y. He, and ——.
    3-partitioning problems for maximizing the minimum load.
    Journal of Combinatorial Optimization. 6(1)(2002), 67-80.
    (A preliminary version, by Lin and Chen, appears in CORSC'96, pages 161-166.)
    1. —— and S. P. Chen.
      On worst-case performance of MLPT applying to 3-partitioning problem.
      In Proceedings of the Fifth Conference of Operations Research Society of China (CORSC'96). Pages 161-166.

2001:

  1. G. L. Xue, —— and D. Z. Du.
    Grade of service Steiner minimum trees in the Euclidean plane.
    Algorithmica. 31(4)(2001), 479-500.
    (An extended abstract, by the same authors, appears in IEEE ISCAS'99, pages VI:182-185.)
    1. G. L. Xue, ——, and D. Z. Du.
      Grade of service Steiner minimum trees in the euclidean plane.
      In Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'99). Vol. VI, 182-185.
  2. —— and G. L. Xue.
    Signed genome rearrangements by reversals and transpositions: models and approximations.
    Theoretical Computer Science. 259(1-2)(2001), 513-531.
    (An extended abstract, by the same authors, appears in COCOON'99, LNCS 1627, pages 71-80.)
    1. —— and G. L. Xue.
      Signed genome rearrangements by reversals and transpositions: models and approximations.
      In Proceedings of the Fifth Annual International Computing and Combinatorics Conference (COCOON'99). LNCS 1627, Pages 71-80.

2000:

  1. D. H. Chen, D. Z. Du, X. D. Hu, ——, L. S. Wang, and G. L. Xue.
    Approximations for Steiner trees with minimum number of Steiner points.
    Journal of Global Optimization. 18(1)(2000), 17-33.
  2. ——, D. S. Kim, and D. Z. Du.
    Strictly nonblocking multirate broadcasting Clos networks.
    Information. 3(3)(2000), 403-413.
    (An extended abstract, by the same authors, appears in PDCS'98, pages 71-80.)
    1. —— D. S. Kim, and D. Z. Du.
      Strictly nonblocking multirate multicast Clos networks.
      In Proceedings of the 10th International Conference on Parallel and Distributed Computing and Systems (PDCS'98)). Pages 417-420.
  3. S.-X. Gao and ——.
    Decision tree complexity of graph properties with dimension at most 5.
    Journal of Computer Science and Technology. 15(5)(2000), 416-422.
  4. D. F. Hsu, X. D. Hu, and ——.
    On minimum-weight k-edge connected Steiner networks on metric spaces.
    Graphs and Combinatorics. 16(3)(2000), 275-284.
    (A preliminary version, by Cui, Hsu, Hu, and Lin, appears in ISORA'96, pages 159-164.)
    1. H. Q. Cui, D. F. Hsu, X. D. Hu, and ——.
      Algorithms for constructing k-connected spanning networks.
      In Proceedings of the Second International Symposium on Operations Research and its Applications (ISORA'96). Pages 159-164.
  5. —— and G. L. Xue.
    Reducing the Steiner problem in four uniform orientations.
    Networks. 35(4)(2000), 287-301.
    (A preliminary version, by the same authors, appears in ISAAC'98, LNCS 1533, pages 327-336.)
    1. —— and G. L. Xue.
      The Steiner tree problem in λ4-geometry.
      In Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98). LNCS 1533, Pages 327-336.

1999:

  1. ——, D. Z. Du, X. D. Hu, and G. L. Xue.
    On rearrangeability of multirate Clos networks.
    SIAM Journal on Computing. 28(4)(1999), 1225-1231.
  2. —— and G. L. Xue.
    Steiner tree problem with minimum number of Steiner points and bounded edge-length.
    Information Processing Letters. 69(2)(1999), 53-57.

1998:

  1. —— and G. L. Xue.
    K-center and k-median problems in graded distances.
    Theoretical Computer Science. 207(1)(1998), 181-192.
  2. ——.
    The exact bound of Lee's MLPT.
    Discrete Applied Mathematics. 85(3)(1998), 251-254.
  3. ——, E. Y. Yao, and Y. He.
    Parallel machines scheduling to maximize the minimum load with non-simultaneous machine available times.
    Operations Research Letters. 22(2-3)(1998), 75-81.

1997:

  1. Y. He and ——.
    Two worst-case performance bounds of LPT algorithm.
    Journal of Zhejiang University. 31(2)(1997), 135-141.
  2. ——, Y. He, H. Y. Lu, and Y. J. Yao.
    Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with non-simultaneous machine available times.
    Applied Mathematics - A Journal of Chinese Universities. 12B(1)(1997), 109-116.

  Last modified: January 20 2012 16:43:16  © Guohui Lin