Proceedings of the 25th Workshop on Combinatorial Mathematics and Computation Theory,Chung Hua University, Hsinchu Hsien, Taiwan, April 25-26, 2008.
Session A1 : Best Papers
1. An Efficient Preprocessing on the One-dimensional Real-scale Pattern Matching Problem ..........................1
Yung-Hsing Peng, Chang-Biau Yang, Chiou-Ting Tseng, Chiou-Yi Hor
2. Loopless Generation of Multi-ary Trees .....................................................................................................10
Ro-Yu Wu, Jou-Ming Chang, Yue-Li Wang
3. The Spanning Fan-connectivity and the Spanning Pipeline-connectivity of Graphs ...................................19
Cheng-Kuan Lin, Jimmy J. M. Tan, D. Frank Hsu, Lih-Hsing Hsu
4. Improved Factoring of RSA Modulus .........................................................................................................26
Jiun-Ming Chen, Shoou-I Yu, Yi Ou-Yang, Po-Han Wang, Chi-Hung Lin, Po-Yi Huang, Bo-Yin Yang, Chi-Sung Laih
5. On the Independent Spanning Trees of Recursive Circulant Graphs G(cdm,d) with d >= 3 .........................34
Jinn-Shyong Yang, Jou-Ming Chang, Shyue-Ming Tang, Yue-Li Wang
6. Protein Structures Alignment Algorithms by Parametric Searching with Trigonometric Series ...................44
Hsiang-Sheng Shin, Yaw-Ling Lin,Wei-De Jiang
7. On the conditional covering problem on paths ...........................................................................................55
Chien-Hsin Lin, Biing-Feng Wang
Session B1 : Interconnection Networks
1. Adjacent vertices fault-tolerance for bipancyclicity of hypercube ...............................................................65
Chun-Nan Hung, Min-Kun Hsiao
2. Hierarchical Crossed Cube: A New Interconnection Topology ...................................................................70
Hong-Chun Hsu, Chang-Hsiung Tsai, Cheng-Hsien Tsai, Guei-Jhuang Wu, Shin-Hao Liu, Pao-Lien Lai
3. Geodesic pancyclicity and balanced 5-pancyclicity of 3-ary n-cube ...........................................................80
Jyun-Hong Guo, Lingling Huang
4. Wide Diameters of (n, k)-Star Graphs .........................................................................................................87
Tsung-Chi Lin, Dyi-Rong Duh
5. The Geodesic Bipancyclicity of the Hypercube ........................................................................................101
Hsien-Yang Liao, Chien-Hung Huang
6. Fault-free Paths in Hypercubes with More Faulty Nodes ..........................................................................108
Tz-Liang Kueng, Tyne Liang, Jimmy J. M. Tan, Lih-Hsing Hsu
Session C1 : Graphs
1. On the Diameter of Geometric Path Graphs of Points in Convex Position ................................................115
Jou-Ming Chang, Ro-Yu Wu
2. Changing the Diameter in Kronecker Product of Cycles ..........................................................................121
Jeng-Jung Wang, Tung-Yang Ho, Ting-Yi Sung
3. The caterpillar factorization of crowns .....................................................................................................126
Hung-Chih Lee, Ming-Ju Lee, Chiang Lin
4. Maintaining Centdians in a Fully Dynamic Forest ....................................................................................131
Hung-Lung Wang
5. The n-Dimensional Burnt Pancake Graph is n*connected ........................................................................139
Li-Ping Yu, Lih-Hsing Hsu
6. An Improved Algorithm for Finding a Length-Constrained Maximum-Density Subtree in a Tree ...........146
Hsin Hao Su, Chin Lung Lu, Chuan Yi Tang
Session D1 : Algorithms & Applications
1. The Game of Un-impartial Kayles ...........................................................................................................151
Kuo-Yuan Kao
2. Fast Squaring Algorithm Design and Complexity Numerical Analyses for Public-Key Cryptosystems ...154
Chia-Long Wu, Der-Chyuan Lou, Te-Jen Chang
3. The Conjugates of Related Primitive Words ............................................................................................162
Chen-Ming Fan, C. C. Huang
4. Windows 視窗化的SEA 演算法具體實現 ............................................................................................167
謝惠婷,楊中皇
5. N 皇后問題的90 度旋轉不動解個數 ...................................................................................................176
謝育平
6. Real-time Reconfigurable Cache for Embedded Systems ........................................................................181
Geng-Cyuan Jheng, Dyi-Rong Duh, and Cheng-Nan. Lai
Session A2 : Bioinformatics & Algorithms
1. Constrained Minkowski Sum Selection and Finding ...............................................................................188
Cheng-Wei Luo, Peng-An Chen, Hsiao-Fei Liu
2. Physiochemical Constraints in Influenza A Hemagglutinin .....................................................................202
Jiunn-I Shieh, Kuei-Jen Lee, Jing-Doo Wang, I-Chun Chen, Am-Chou Chen, Pei-Chun Chang, Hsiang-Chuan Liu
3. A new tree comparison metric - the mixture distance for the mixture trees .............................................207
Chen-Hui Lin, Justie Su-Tzu Juan
4. Finding Winner Alignments with Multiple Scoring Matrices ...................................................................212
Kuo-Tsung Tseng, Chang-Biau Yang, Yung-Hsing Peng, Chiou-Ting Tseng
5. A hybrid method of feature selection for microarray gene expression data .............................................219
Cheng-San Yang, Li-Yeh Chuang, Chao-Hsuan Ke, Cheng-Hong Yang
Session B2 : String Algorithms
1. Fast Algorithms for the Constrained Longest Increasing Subsequence Problems ....................................226
I-Hsuan Yang, Yi-Ching Chen
2. An Exact String Matching Algorithm Based upon the Single Character Matching Mechanism ...............232
K. W. Liu, R. C. T. Lee
3. An Approximate String Matching Algorithm Based upon the Candidate Elimination Method ................238
C. W. Lu, R. C. T. Lee
4. Finding All Approximate Palindromes ....................................................................................................242
L. C. Chen, R. C. T. Lee
5. An Exact String Matching Algorithm Based upon the Substring Encoding Method ................................246
H. M. Chen, R. C. T. Lee
Session C2 : Graphs
1. Second Medians and Second Centroids of Weighted Trees .....................................................................251
Chiang Lin, Jen-Ling Shang
2. A certifying algorithm for the path cover problem on interval graphs .....................................................255
Maw-Shang Chang
3. On Greedy Edge Set Partitions of Graphs by Cliques ..............................................................................263
Tao-Ming Wang, Jun-Lin Kuo
4. Optimal geodesic cycles embedding of Mobius cubes ............................................................................269
Chang-Hsiung Tsai, Jheng-Cheng Chen, Pao-Lien Lai, Hong-Chun Hsu
5.簡介演算法研究的三個新興議題 .........................................................................................................276
張貿翔
Session D2 : Network Algorithms
1. Expected Quorum Overlap Sizes of Optimal Quorum Systems with the Rotation Closure Property for
Asynchronous Power-Saving Algorithms in Mobile Ad Hoc Networks ...................................................283
Jehn-Ruey Jiang
2.無線感測網路上以調整感測半徑來延長目標監控之生命週期 .........................................................295
吳建意, 俞征武, 索維廷
3. A Simple kNN Search Protocol using Data Broadcasting in Wireless Mobile Environments ...................303
Kai-Yun Ho, Chuan-Ming Liu, Chien-Hung Liu
4. 一個在動態環境下的最短路徑搜尋演算法 .........................................................................................311
陳弘升,劉傳銘,廖明傑
5. Randomized Coverage Algorithms for Mobile Sensor Networks .............................................................318
Chang Wu Yu
Session A3 : Algorithms & Graphs
1. A Linear Time Algorithm for Solving the Incidence Coloring Problem on Strongly Chordal Graphs ......325
Yen-Ju Chen, Shyue-Ming Tang, Yue-Li Wang
2. A Hybrid Genetic Algorithm for Minimizing Total Flowtime in Flowshop Scheduling Problems ............331
曾怜玉,林亞泰
3.以優先權選擇的混合式基因演算法解決旅行家問題 .........................................................................339
胡哲維,林葭華
4. A New Heuristic Method for Simple Plant Location Problem ..................................................................347
曾怜玉,吳志盛
5. The Weighted All-Pairs-Shortest-Path-Length Problem on Two-Terminal Series-Parallel Graphs ............354
William Chung-Kung Yen , Shuo-Cheng Hu, Tai-Chang Chen
Session B3:Image Processing & Interconnection Networks
1.植基於PDE 修補方法且具強韌性之影像竄改偵測及還原技術 .........................................................362
洪國龍,陳璟慶
2. On Secret Multiple Image Sharing ...........................................................................................................369
Shyong Jian Shyu, Ying-Ru Chen
3. Edge Fault Tolerance for Two-Pair Spanning Disjoint Paths of Star Networks .........................................375
Chun-Nan Hung, Chi-Lai Liu, Hsuan-Han Chang
4.基於邊緣方向的混合式彩色濾鏡陣列內插法 .....................................................................................385
席家年,陳瀅如,王志文
5. Digital Image Watermarking with 1/T Rate Forward Error Correction to Malicious Attacks ....................390
Wei-Hung Lin, Shi-Jinn Horng, Tzong-Wann Kao, Yuh-Rau Wang, Cheng-Ling Lee, Yi Pan
Session C3 : Graphs
1. On the minimum density of 2-clique and 3/2-clique in directed graphs ...................................................398
Bang Ye Wu, Lingling Huang, Chen-Ying Lin
2. Finding Hamiltonian Cycle on Cartesian Product of a Hypotraceable Graph and a Hamiltonian Graph ..402
Yung-Ling Lai, Jin-Long Lin
3. A DNA-Based Solution to the Subgraph Isomorphism Problem ..............................................................407
Sun-Yuan Hsieh, Chao-Wen Huang
4. A fast graph algorithm for genus-2 hyperelliptic curve discrete logarithm Problems ...............................414
Chia-Wei Lin, Rong-Jaye Chen
5. On The Total Product Cordial Labeling of Pn+mK1 ..................................................................................420
Yung-Ling Lai, Yi-Ming Chen
6. Constructing Optimal Rank-Decomposition Trees of Biconnected Outerplanar Graphs ...........................424
Sheng-Lung Peng, Guan-Da Chen, Hsiang-Yu Tsou, In-Te Li, Yan-Fang Li
Session D3 : Algorithms & Applications
1.基於字尾樹演算法之避免交互雜交DNA 微陣列探針集合自動化選擇研究 ....................................429
林婉婷,侯玉松,吳哲賢
2.生物晶片之不相交雙探針辨識問題 .....................................................................................................435
吳哲賢,侯玉松
3. Incremental Learning with Support Vector Machines and Fuzzy Set Theory ...........................................440
Yu-Ming Chuang, Cha-Hwa Lin
4.一個有效解決SDH 網路頻寬重組問題的演算法 .................................................................................445
張家榮,張志清, 蔡英德
5.前後文無關文法於語音合成語料庫設計之應用 .................................................................................455
黃奕欽, 陳嘉平