Proceedings of the 27th Workshop on Combinatorial Mathematics and Computation Theory,

Providence University, Taichung, Taiwan, April 30-May 1, 2010

Session A1：Best Papers

  1. Constructing Many-to-One Vertex-Disjoint Paths in (n, k)-Star Graphs........................................................................................................ 2

    2. Tsung-Chi Lin, Dyi-Rong Duh and Hsien-Jone Hsieh

  2. Bit-Parallel Operations to Investigate Properties of Logical Vectors by Logical Operations............................................................................ 15

    3. C. S. Ou and R. C. T. Lee

  3. Multiple-Pattern Matching Using Improved Bit-Parallel Approach................................................................................................................. 21

    4. K. H. Chen, G. S. Huang and R. C. T. Lee

  4. Sufficient conditions for the non-separating paths........................................................................................................................................... 27

    5. Bang Ye Wu and Hung-Chou Chen

  5. Algorithms for the Hybrid Constrained Longest Common Subsequence Problem............................................................................................ 32

    6. Yi-Ching Chen

  6. A Diophantine Problem in EXP*................................................................................................................................................................... 38

    7. Shih Ping Tung

Session B1：Algorithms & Bioinformatics

  1. A Progressive Strategy for DNA Resequencing Problem................................................................................................................................ 45

    2. Chia-Wei Lu, Chuan-Yi Tang and R. C. T. Lee

  2. 機器學習用於疾病預測............................................................................................................................................................................. 50

    3. 莊麗月、吳國銓、張學偉、楊正宏

  3. DOBALI: a Domain-based Multiple Sequence Alignment Tool....................................................................................................................... 56

    4. Guang-Yen Chang, Chin-Liang Tsai, Tsung-Lun Wu, Cheng-Wen Chang and Chuan Yi Tang

  4. An Effective Tool Preference Selection Method for Protein Structure Prediction with SVM *.......................................................................... 62

    5. Hsin-Wei Yen, Chang-Biau Yang and Hsing-Yen Ann

  5. 基因重組之字首反轉排序最佳解上限值問題 ........................................................................................................................................ 68

    6. 吳哲賢、張正佳

Session C1：Graphs

  1. Node congestion and bisection width of a k-ary n-Cube................................................................................................................................ 75

    2. Jeng-Jung Wang and Ting-Yi Sung

  2. On Fault Tolerance Of D 3,2,1 -Domination *............................................................................................................................................... 80

    3. Yung-Ling Lai, Shih-Shian Chuang and Shih-Ping Huang

  3. Weak Roman Domination on Block Graphs.................................................................................................................................................. 86

    4. Chih-Shan Liu, Sheng-Lung Peng and Chuan Yi Tang

  4. Queue layouts on folded hypercubes FQn with n <= 7................................................................................................................................... 90

    5. Kung-Jui Pai, Jou-Ming Chang and Yue-Li Wang

  5. Displacements of Weighted Graphs............................................................................................................................................................... 96

    6. Chiang Lin and Jen-Ling Shang

Session A2：Interconnection Networks

  1. Adjacent vertex fault tolerance for two spanning disjoint paths of hypercube................................................................................................... 103

    2. Chun-Nan Hung and Wan-Chen Sung

  2. Embedding a Family of Two Disjoint Multi-dimensional Meshes into Locally Twisted Cubes *....................................................................... 112

    3. Cheng-Yi Lin, Jou-Ming Chang, Jinn-Shyong Yang and Hung-Chang Chan

  3. Pancyclicity on Generalized Recursive Circulant Graphs *.............................................................................................................................. 118

    4. Chien–Yi Li, Shyue–Ming Tang, and Yue–Li Wang

  4. The two-equal-disjoint path cover problem of the hierarchical crossed cube *................................................................................................ 124

    5. Chih-Min Chien, Jheng-Cheng Chen, Pao-Lien Lai, Cheng-Hsuing Tsai and Hong-Chun Hsu

  5. Mutually Independent Hamiltonian Cycle of Burnt Pancake Graphs................................................................................................................ 134

    6. Yung-Ling Lai and Da-Chung Yu

Session B2：Algorithms & Bioinformatics

  1. Comparisons of Semi-local Alignment Algorithms for Protein Structures......................................................................................................... 142

    2. Hong-Shin Chen and Yaw-Ling Lin

  2. 一個快速的啟發式演算法在一致性分割問題上..................................................................................................................................... 149

    3. Yen Hung Chen, Shin Hung Chen and Yu Hung Hsiao

  3. Confronting Two-Pair Primer Design using Memetic Algorithm....................................................................................................................... 155

    4. Cheng-Hong Yang, Yu-Huei Cheng and Li-Yeh Chuang

  4. A Parallel Approach to Solve the Approximation String Matching Problem..................................................................................................... 161

    5. C. S. Ou and R. C. T. Lee

Session C2：Graphs

  1. The Connected p-Median Problem on Graphs with Forbidden Vertices.......................................................................................................... 168

    2. William Chung-Kung Yen, Shun-Chieh Chang, Shung Chih-Shiang Yang and Shou-Cheng Hu

  2. 3*-Connectivity of the Fully Connected Cubic Networks................................................................................................................................ 174

    3. Lih-Hsing Hsu and Kuo-Tung Lai

  3. Spanning Connectivity of the WK-Recursive Networks.................................................................................................................................. 180

    4. Hui-Chen Ho, Tung-Yang Ho and Lih-Hsing Hsu

  4. A Linear-time Algorithm for Broadcast Domination Problem on Interval Graphs.............................................................................................. 184

    5. Ruei-Yuan Chang and Sheng-Lung Peng

  5. Some 3-regular 4-ordered graphs *............................................................................................................................................................... 189

    6. Lih-Hsing Hsu

Session A3：Interconnection Networks

  1. Fault Hamiltonicity of Hierarchical Restricted HL-Graphs *............................................................................................................................ 196

    2. Shang-Wun Huang, Pao-Lien Lai, Chang-Hsiung Tsai and Hong-Chun Hsu

  2. The Hamiltonian cycle and Hamiltonian paths passing through prescribed edges in a star graph with faulty edges *........................................... 207

    3. Chun-Nan Hung and Tsung-Yu Yu

  3. Balanced pancyclicity of the generalized base-b hypercube............................................................................................................................. 216

    4. Jywe-Fei Fang, Yi-Wei Hsu, Yi-Chung Lin, Xiao-Peng Huang and Hong-Ren Chen

  4. Adjacent Vertices Fault-Tolerance Bifanability of Hypercube with the Same Color Sources *......................................................................... 223

    5. Chun-Nan Hung and Cing-Jhan Yan

Session B3：Algorithms & Combinatorial Math

  1. On the Complexity of the Linear Sliding-Coin Puzzle...................................................................................................................................... 233

    2. Ting-Yu Lin, Shi-Chun Tsai, Wen-Nung Tsai and Jong-Chuang Tsay

  2. The Local Harmonious Chromatic Problem *................................................................................................................................................. 237

    3. Yue-Li Wang, Tsong-Wuu Lin and Lin-Yuan Wang

  3. A Simple Proof for the Hamiltonian Property on Rotation Graphs of Binary Trees........................................................................................... 249

    4. Ro-Yu Wu and Hung-Lung Wang

Session C3：Graphs

  1. On Distance-Two Domination of Composition of Graphs *............................................................................................................................ 255

    2. Yung-Ling Lai and Shou-Bo Jeng

  2. Prefix-Primitive Annihilators of Languages *................................................................................................................................................... 258

    3. Chen-Ming Fan and Cheng-Chih Huang

  3. Appropriate Item Partition for Improving the Mining Performance................................................................................................................... 263

    4. Tzung-Pei Hong, Jheng-Nan Huang, Kawuu W. Lin and Wen-Yang Lin

  4. Fault-tolerant Hamiltonicity of Dual-cube Extensive Networks *...................................................................................................................... 268

    5. Shih-Yan Chen and Shin-Shin Kao