[ Conference Proceedings Publications | Edited Works | Others ]

Journal publications (Algorithmsleft, Bioinformaticsright) 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 2014 2015 2016 2017  2018
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.
  • Co-first authors by , correspondence authors by *.
  • Conference proceedings publications as extended abstract listed under the respective journal articles.
Informal publications at arXiv:
  1. Y. Xu, Y. Chen, T. Luo, and ——*.
    A local search 2.917-approximation algorithm for duo-preservation string mapping.
    (2017) CoRR abs/1702.01877.
  2. W. Luo, T. Luo, R. Goebel, and ——*.
    On rescheduling due to machine disruption while to minimize the total weighted completion time.
    (2017) CoRR abs/1701.07498.
  3. Y. Xu, P. Zhang, R. Goebel, and ——*.
    Approximation algorithms for the vertex happiness.
    (2017) CoRR abs/1606.03185.
  4. W. Tong, Z.-Z. Chen, L. Wang, Y. Xu, J. Xu, R. Goebel, and ——*.
    An approximation algorithm for the Bandpass-2 problem.
    (2013) CoRR abs/1307.7089.
In press:
  1. W. Tong, E. Miyano, R. Goebel, and ——*.
    An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops.
    Theoretical Computer Science. (SI on FAW 2016).
    Accepted on September 21, 2017.
    1. W. Tong, E. Miyano, R. Goebel, and ——*.
      A PTAS for multiple parallel identical multi-stage flowshops to minimize the makespan.
      In Proceedings of the 10th International Frontiers of Algorithmics Workshop (FAW 2016). LNCS 9711, pages 227-237.
  2. W. Luo, Y. Xu, B. Gu, W. Tong, R. Goebel, and ——*.
    Algorithms for communication scheduling in data gathering network with data compression.
    Algorithmica.
    Accepted on June 23, 2017.
  3. P. Zhang, Y. Xu, T. Jiang, A. Li, ——*, and E. Miyano.
    Improved approximation algorithms for the maximum happy vertices and edges problems.
    Algorithmica.
    Accepted on March 3, 2017.
  4. J. Dong, X. Wang, J. Hu, and ——*.
    Single machine scheduling with job delivery to multiple customers.
    Journal of Scheduling.
    Accepted on January 12, 2017.

    1. Y. Xu, Y. Chen, ——*, T. Liu, T. Luo, and P. Zhang*.
      A (1.4 + ε)-approximation algorithm for the 2-Max-Duo problem.
      In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017).
      LIPIcs 92, pages 66:1-66:12.

    2. Z.-Z. Chen*, ——*, L. Wang, Y. Chen, and D. Wang.
      Approximation algorithms for the maximum weight internal spanning tree problem.
      In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017). LNCS 10392, pages 124-136.
      Abstract: Given a vertex-weighted connected graph G = (V, E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of the internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3 - ε, for any ε > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm.

    3. W. Luo, Y. Xu, W. Tong, and ——*.
      Single machine scheduling with job-dependent machine deterioration.
      In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016). LIPIcs 64, pages 55:1-55:13.
      Abstract: We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum; in the full maintenance case every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case has been proven NP-hard; several special cases of the problem in the partial maintenance case were shown solvable in polynomial time, but the complexity of the general problem is left open. In this paper we first prove that the problem in the partial maintenance case is NP-hard, thus settling the open problem; we then design a 2-approximation algorithm.

    1. W. Tong and ——*.
      An improved approximation algorithm for the minimum common integer partition problem.
      In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014). LNCS 8889, Pages 353-364.
      Abstract: Given a collection of multisets {X1, X2, ..., Xk} (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset Xi, 1 ≤ ik. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for X1, X2, ..., Xk with the minimum cardinality. We present a 6⁄5-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of ratio 5⁄4 designed in 2006. We then extend it to obtain an absolute 0.6k-approximation algorithm for k-MCIP when k is even (when k is odd, the approximation ratio is 0.6k+0.4).
    2. W. Tong, R. Goebel, W. Ding, and ——*.
      An improved approximation algorithm for the Bandpass problem.
      In Proceedings of the Joint Conference of the Sixth International Frontiers of Algorithmics Workshop and the Eighth International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM 2012). LNCS 7285, Pages 351-358.
      Abstract: The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B2). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a 36⁄19-approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.
 

    1. Y. Shi*, X. Zhang, X. Liao, ——, and D. Schuurmans.
      Protein-chemical interaction prediction via kernelized sparse learning SVM.
      In Proceedings of Pacific Symposium on Biocomputing 2013 (PSB 2013). 18(2013), Pages 41-52.
2017:
  1. J. Dong, J. Hu, M. Y. Kovalyov, ——*, T. Luo, W. Tong, X. Wang, and Y. Xu.
    Corrigendum to "An FPTAS for the parallel two-stage flowshop problem. Theoretical Computer Science, 657: 64-72 (2017)".
    Theoretical Computer Science. 687(2017), 93-94.
  2. J. Dong, W. Tong, T. Luo, X. Wang, J. Hu, Y. Xu, and ——*.
    An FPTAS for the parallel two-machine flowshop problem.
    Theoretical Computer Science. 657(Part A)(2017), 64-72.
 
2016:
  1. J. Hu, T. Luo, X. Su, J. Dong, W. Tong, R. Goebel, Y. Xu, and ——*.
    Machine scheduling with a maintenance interval and job delivery coordination.
    Optimization Letters. 10(8)(2016), 1645-1656.
    1. J. Hu, T. Luo, X. Su, J. Dong, W. Tong, R. Goebel, Y. Xu, and ——*.
      Machine scheduling with a maintenance interval and job delivery coordination.
      In Proceedings of the Ninth International Frontiers of Algorithmics Workshop (FAW 2015). LNCS 9130, Pages 104-114.
  2. J. Dong, X. Wang, J. Hu, and ——*.
    An improved two-machine flowshop scheduling with intermediate transportation.
    Journal of Combinatorial Optimization. 31(3)(2016), 1316-1334.
  3. H. Zhang, W. Tong, Y. Xu, and ——*.
    The Steiner traveling salesman problem with online advanced edge blockages.
    Computers and Operations Research. 70(2016), 26-38.
  4. J. Dong, J. Hu, and ——*.
    A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines.
    Optimization Letters. 10(1)(2016), 109-118.
  5. W. Tong, R. Goebel, and ——*.
    On the smoothed heights of Trie and Patricia index trees.
    Theoretical Computer Science. 609(Part 3: SI on COCOON 2014)(2016), 620-626.
    1. W. Tong, R. Goebel, and ——*.
      On the smoothed heights of Trie and Patricia index trees.
      In Proceedings of the 20th International Computing and Combinatorics Conference (COCOON 2014). LNCS 8591, Pages 94-103.
 


  1. Y. Wu, F. Streijger, Y. Wang, ——, S. Christie, J.-M. Mac-Thiong, S. Parent, C. Bailey, S. Paquette, M. Boyd, T. Ailon, J. T. Street, C. Fisher, M. Dvorak, B. Kwon*, and L. Li*.
    Parallel metabolomic profiling of cerebrospinal fluid and serum for identifying biomarkers of injury severity after acute human spinal cord injury.
    Scientific Reports. 6(2016), 38718.
    Abstract: Suffering an acute spinal cord injury (SCI) can result in catastrophic physical and emotional loss. Efforts to translate novel therapies in acute clinical trials are impeded by the SCI community's singular dependence upon functional outcome measures. Therefore, a compelling rationale exists to establish neurochemical biomarkers for the objective classification of injury severity. In this study, CSF and serum samples were obtained at 3 time points (~24, 48, and 72 hours post-injury) from 30 acute SCI patients (10 AIS A, 12 AIS B, and 8 AIS C). A differential chemical isotope labeling liquid chromatography mass spectrometry (CIL LC-MS) with a universal metabolome standard (UMS) was applied to the metabolomic profiling of these samples. This method provided enhanced detection of the amine- and phenol-containing submetabolome. Metabolic pathway analysis revealed dysregulations in arginine-proline metabolism following SCI. Six CSF metabolites were identified as potential biomarkers of baseline injury severity, and good classification performance (AUC > 0.869)s was achieved by using combinations of these metabolites in pair-wise comparisons of AIS A, B and C patients. Using the UMS strategy, the current data set can be expanded to a larger cohort for biomarker validation, as well as discovering biomarkers for predicting neurologic outcome.
2015:

  1. I. Kanj, ——, T. Liu, W. Tong, G. Xia, J. Xu, B. Yang, F. Zhang, P. Zhang*, and B. Zhu.
    Improved parameterized and exact algorithms for cut problems on trees.
    Theoretical Computer Science. 607(Part 3: SI on COCOA 2014)(2015), 455-470.
    1. I. Kanj, ——, T. Liu, W. Tong, G. Xia*, J. Xu, B. Yang, F. Zhang, P. Zhang, and B. Zhu.
      Algorithms for cut problems on trees.
      In Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2014). LNCS 8881, Pages 283-298.
  2. F. Y. L. Chin, B. Fu, J. Guo, S. Han, J. Hu, M. Jiang, ——, H.-F. Ting, L. Zhang, Y. Zhang*, and D. Zhou.
    Competitive algorithms for unbounded one-way trading.
    Theoretical Computer Science. 607(Part 1: SI on AAIM 2014)(2015), 35-48.
  3. L. Huang, W. Tong, R. Goebel, T. Liu, and ——*.
    A 0.5358-approximation for Bandpass-2.
    Journal of Combinatorial Optimization. 30(2015), 612-626.
  4. H. Zhang, W. Tong, Y. Xu, and ——*.
    The Steiner traveling salesman problem with online edge blockages.
    European Journal of Operational Research. 243(2015), 30-40.
    Abstract: We consider the online Steiner Traveling Salesman Problem. In this problem, we are given an edge-weighted graph G = (V, E) and a subset DV of destination vertices, with the optimization goal to find a minimum weight closed tour that traverses every destination vertex of D at least once. During the traversal, the salesman could encounter at most k non-recoverable blocked edges. The edge blockages are real-time, meaning that the salesman knows about a blocked edge whenever it occurs. We first show a lower bound on the competitive ratio and present an online optimal algorithm for the problem. While this optimal algorithm has non-polynomial running time, we present another online polynomial-time near optimal algorithm for the problem. Experimental results show that our online polynomial-time algorithm produces solutions very close to the offline optimal solutions.
 

  1. Abstract: We report an analytical tool to facilitate metabolite identification based on an MS/MS spectral match of an unknown to a library of predicted MS/MS spectra of possible human metabolites. To construct the spectral library, the known endogenous human metabolites in the Human Metabolome Database (HMDB) (8,021 metabolites) and their predicted metabolic products via one metabolic reaction in the Evidence-based Metabolome Library (EML) (375,809 predicted metabolites) were subjected to in silico fragmentation to produce the predicted MS/MS spectra. This spectral library is hosted at the public MCID Web site (www.MyCompoundID.org), and a spectral search program, MCID MS/MS, has been developed to allow a user to search one or a batch of experimental MS/MS spectra against the library spectra for possible match(s). Using MS/MS spectra generated from standard metabolites and a human urine sample, we demonstrate that this tool is very useful for putative metabolite identification. It allows a user to narrow down many possible structures initially found by using an accurate mass search of an unknown metabolite to only one or a few candidates, thereby saving time and effort in selecting or synthesizing metabolite standard(s) for eventual positive metabolite identification.


  2. T. Huan, Y. Wu, C. Tang, ——, and L. Li*.
    DnsID in MyCompoundID for rapid identification of Dansylated Amine- and Phenol-containing metabolites in LC-MS-based metabolomics.
    Analytical Chemistry. 87(19)(2015), 9838-9845.
  3. H. Jiang, ——, W. Tong, D. Zhu, and B. Zhu*.
    Isomorphism and similarity for 2-generation pedigrees.
    BMC Bioinformatics. 16(Suppl 5: SI for ISBRA'14)(2015), S7.
    1. H. Jiang, ——, W. Tong, B. Zhu*, and D. Zhu.
      Isomorphism and similarity for 2-generation pedigrees.
      In Proceedings of the 10th International Symposium on Bioinformatics Research and Applications (ISBRA 2014). LNCS/LNBI 8492, Page 396.
2014:
  1. W. Tong, R. Goebel, T. Liu, and ——*.
    Approximating the maximum multiple RNA interaction problem.
    Theoretical Computer Science. 556(SI on COCOA 2013)(2014), 63-70.
    1. W. Tong, R. Goebel, T. Liu, and ——*.
      Approximation algorithms for the maximum multiple RNA interaction problem.
      In Proceedings of the 7th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2013). LNCS 8287, Pages 49-59.

  2. W. Tong, R. Goebel, and ——*.
    Approximating the minimum independent dominating set in perturbed graphs.
    Theoretical Computer Science. 554(SI on COCOON 2013)(2014), 275-282.
    1. W. Tong, R. Goebel, and ——*.
      Approximating the minimum independent dominating set in perturbed graphs.
      In Proceedings of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013). LNCS 7936, Pages 257-267.
  3. Z. Chen, B. Fu, R. Goebel, ——, W. Tong, J. Xu, B. Yang, Z. Zhao, and B. Zhu*.
    On the approximability of the exemplar adjacency number problem for genomes with gene repetitions.
    Theoretical Computer Science. 550(2014), 59-65.
 

  1. Y. Tang, R. Li, ——, and L. Li*.
    PEP search in MyCompoundID: detection and identification of dipeptides and tripeptides using dimethyl labeling and hydrophilic interaction liquid chromatography tandem mass spectrometry.
    Analytical Chemistry. 86(7)(2014), 3568-3574.
    Abstract: Small peptides, such as dipeptides and tripeptides, are naturally present in many biological samples (e.g., human biofluids and cell extracts). They have attracted great attention in many research fields because of their important biological functions as well as potential roles as disease biomarkers. Tandem mass spectrometry (MS/MS) can be used to profile these small peptides. However, the type and number of fragment ions generated in MS/MS are often limited for unambiguous identification. Herein we report a novel database-search strategy based on the use of MS/MS spectra of both unlabeled and dimethyl labeled peptides to identify and confirm amino acid sequences of di/tripeptides that are separated using hydrophilic interaction (HILIC) liquid chromatography (LC). To facilitate the di/tripeptide identification, a database consisting of all the predicted MS/MS spectra from 400 dipeptides and 8,000 tripeptides was created and a search tool, PEP Search, was developed and housed at the MyCompoundID website (www.mycompoundid.org/PEP). To evaluate the identification specificity of this method, we used acid hydrolysis to degrade a standard protein, cytochrome c, to produce many di/tripeptides with known sequences for LC-MS/MS. The resultant MS/MS spectra were searched against the database to generate a list of matches which were compared to the known sequences. We correctly identified all the di/tripeptides produced from the protein hydrolysate. We then applied this method to detect and identify di/tripeptides naturally present in human urine samples with confidence. We envisage the use of this method as a complementary tool to various LC-MS techniques currently available for small molecule or metabolome profiling with an added benefit of covering all di/tripeptide chemical space.
2013:
 

  1. H. Sabaa, Z. Cai, Y. Wang, R. Goebel, S. Moore, and ——*.
    Whole genome identity-by-descent determination.
    Journal of Bioinformatics and Computational Biology. 11(2)(2013), 1350002 (19 pages).

  2. L. Li*, R. Li, J. Zhou, A. Zuniga, A. E. Lewis-Stanislaus, Y. Wu, T. Huan, J. Zheng, Y. Shi, D. S. Wishart, and ——.
    MyCompoundID: Using an evidence-based metabolome library for metabolite identification.
    Analytical Chemistry. 85(6)(2013), 3401-3408.
    Abstract: Identification of unknown metabolites is a major challenge in metabolomics. Without the identities of the metabolites, the metabolome data generated from a biological sample cannot be readily linked with the proteomic and genomic information for studies in systems biology and medicine. We have developed a web-based metabolite identification tool that allows searching and interpreting mass spectrometry (MS) data against a newly constructed metabolome library composed of 8,021 known human endogenous metabolites and their predicted metabolic products (375,809 compounds from one metabolic reaction and 10,583,901 from two reactions). As an example, in the analysis of a simple extract of human urine or plasma and the whole human urine by liquid chromatography-mass spectrometry and MS/MS, we are able to identify at least two times more metabolites in these samples than by using a standard human metabolome library. In addition, it is shown that the evidence-based metabolome library (EML) provides a much superior performance in identifying putative metabolites from a human urine sample, compared to the use of the ChemPub and KEGG libraries.
2012:

  1. H. Jiang, Z. Li, ——, L. Wang, and B. Zhu*.
    Exact and approximation algorithms for the complementary maximum strip recovery problem.
    Journal of Combinatorial Optimization. 23(4)(2012), 493-506.
  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. 78(3)(2012), 720-730.
    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.
 
  1. Y. Shi*, B. Yuan, ——, and D. Schuurmans.
    Protein phosphorylation site prediction via feature discovery support vector machine.
    Tsinghua Science & Technology. 17(6; SI on Bioinformatics and Computational Biology)(2012), 638-644.

  2. M. Berjanskii, J. Zhou, Y. Liang, ——, and D. S. Wishart*.
    Resolution-by-proxy: a simple measure for assessing and comparing the overall quality of NMR protein structures.
    Journal of Biomolecular NMR. 53(3)(2012), 167-180.
  3. 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. 4(2)(2012), 1250023 (20 pages).
    (Two preliminary versions appear in COCOA 2010, LNCS 6509, Pages 85-103, and COCOA 2009, LNCS 5573, Pages 73-84.)
    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.
  4. 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. Li and ——*.
    The three column Bandpass problem is solvable in linear time.
    Theoretical Computer Science. 412(4-5)(2011), 281-299.
  5. 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.
 

  1. 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.
2010:

  1. 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.
 
  1. 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.
    Nucleic Acids Research. 38(Web Server issue)(2010): W633-W640.

  2. 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.
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.
    (An extended abstract of an earlier version with performance ratio 3.5375, by Z. Cai, Z.-Z. Chen, ——*, and L. Wang, appears in COCOA 2008, LNCS 5165, pages 286-295.)
    1. Z. Cai, Z.-Z. Chen, ——, and L. Wang.
      An improved approximation algorithm for the capacitated multicast tree routing problem.
      In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08). LNCS 5165, Pages 286-295.

  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. 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.
    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. G. N. Lin, Z. Cai, ——, S. Chakraborty, and D. Xu*.
    ComPhy: prokaryotic composite distance phylogenies inferred from whole-genome gene sets.
    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).

  7. 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.
    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. 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.
    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.
    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. Y. Shi, J. Zhou, D. Arndt, D. S. Wishart*, and ——*.
    Protein contact order prediction from primary sequences.
    BMC Bioinformatics. 9(2008): 255(30May2008).
    (A poster by Zhou, Shi, Lin, and Wishart, presented in CPI'07.)
  6. 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.
    Nucleic Acids Research. 36(Database Issue)(2008), D222-D229.

2007:

  1. (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. 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. 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. (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. 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. 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.
    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. 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: September 21 2017 12:59:39  © Guohui Lin