Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, Kaohsiung, Taiwan, Mar. 29-30, 2002.
Session A1 Graph Algorithms (1)
1. Independent Spanning Trees on Two-dimension Tori ...................................................................................................1
Shyue-Ming Tang, Yue-Li Wang
2. A Linear-Time Algorithm for the Hamiltonian Problem on Distance-Hereditary Graphs ........................................................ 8
Sun-Yuan Hsieh, Chin-wen Ho, Tsan-sheng Hsu, Ming Tat Ko
3. Strong Distance of Complete Bipartite Graphs..................................................................................................................... 12
Yung-Ling Lai, Feng-Hsu Chiang, Chu-He Lin, Tung-Chin Yu
4. Construction for Strongly k-Hamiltonian Graphs ................................................................................................................. 17
Chun-Nan Hung, Xiao-Shen Zhu
5. Distributed Algorithms of Finding the Unique Minimum Distance Dominating Set in Directed Split-Stars ...................................23
Fu-Hsing Wang, Jou-Ming Chang, Yue-Li Wang
Session B1 Computational Biology
1. Approximating the two-source minimum routing cost spanning trees of metric graphs ............................................................. 29
Bang Ye Wu
2. On the Optimum Requirement Graph Problem .................................................................................................................. 35
Kun-Mao Chao, B. Y. Wu, C. Y. Tang
3. Identifying GC-Rich DNA Segments via Linear-Time Algorithm for Maximum Average Binary Substring ............................... 40
Hsueh-I Lu
4. 生物序列比對問題上考慮凸形間隔處罰函數的一些O(nm)演算法 ................................................................................. 47
吳哲賢、王志倫
5. An Efficient Algorithm for Multiple Sequence Alignment .................................................................................................... 50
Kuen-Feng Huang, Chang-Biau Yang, Kuo-Tsung Tseng
Session A2 Graph Algorithms (2)
1. An O(n) Algorithm for Finding a Tree 3-spanner on Permutation Graphs ............................................................................ 60
Hon-Chan Chen and Shin-Huei Wu
2. The clique tranversal and clique independence of distance-hereditary graphs ........................................................................ 64
M. S. Chang, C. M. Lee, S. C. Sheu
3. A Linear Algorithm for the Connected Domination Problem on Circular-Arc Graphs ............................................................. 70
Ruo-Wei Hung, Maw-Shang Chang
4. Some Optimal Parallel Algorithms for Shortest Path Related Problems on Interval and Circular-arc Graphs............................. 79
F. R. Hsu, M. K. shan, H. S. Chao, R. C. T. Lee
Session B2 Interconnection Networks (1)
1. A Routing Scheme for Constructing Node-to-Node Disjoint Paths in Alternating Group Graphs ............................................ 89
Chin-Tsai Lin, Wen-Chung Chiu
2. Embedding of Tree Machines into Hypercubes ................................................................................................................ 100
Chui-Cheng Chen
3. Fault Hamiltonicity of the Shuffle-Cubes ......................................................................................................................... 110
Tseng-Kuei Li, Jimmy J. M. Tan, Lih-Hsing Hsu
4. Lower bound study for the concurrent multicast from multiple sources .............................................................................. 120
Wen-Lin Yang
Session A3 Image Processing
1. Design a Morphological De-ringing Filter of Ultrasound Images .......................................................................................... 130
Shen-Chuan Tai, Yen-Yu Chen, and Shin-Feng Sheu
2. Color Image Compression Using Spread Grey-Based Neural Networks in the Transform Domain ......................................... 137
Chi-Yuan Lin, Chin-Hsing Chen
3. A User Friendly Implementation of Smart Card Access with Threshold Scheme .................................................................. 146
Shyi-Tsong Wu and Bin-Chang Chieu
Session B3 Interconnection Networks (2)
1. Fault-Tolerant Routing For Pyramid Networks Using Least Level Minimal Routing Method ................................................. 152
Da-Ren Chen, Chiun-Chieh Hsu
2. On Minimizing the Maximum Congestion for Weighted Hypergraph Embedding in a Cycle .................................................. 160
Sing-Ling Lee, Hann-Jang Ho
3. Cycle Embedding in the Hypercube with Faulty Nodes .................................................................................................... 166
Jung-Sheng Fu
Session A4 Combinatorial Algorithms
1. On Exponential-Time Completeness of the Circularity Problem for Attribute Grammars ..................................................... 173
Pei-Chi Wu
2. An Efficient Algorithm for Finding Maximal Mean Sequence ............................................................................................ 177
Chun-Chao Yeh, Chun-Hsin Wu
3. The conditional location of a median path ....................................................................................................................... 183
B. F. Wang, S-C. Ku, and Y. H. Hsieh
4. A Space-efficient Godel Numbering with Chinese Remainder Theorem ............................................................................. 192
Shi-Chun Tsai, Jen-Chun Chang, Rong-Jaye Chen
5. Fibonacci Search with Multiple Probes ........................................................................................................................... 196
Yaw-Ling Lin and Shi-Chun Tsai
Session B4 Parallel Algorithms
1. The CFS and ED Data Distribution Schemes for Sparse Arrays on Distributed Memory Multicomputers.............................. 199
Chun-Yuan Lin, Yeh-Ching Chung, Jen-Shiuh Liu
2. Optimal parallel algorithms for the 3D Euclidean distance transform on the CRCW and EREW PRAM models .................... 209
Yuh-Rau Wang, Shi-Jinn Horng, Yu-Hua Lee, Pei-Zong Lee
3. Systolic Algorithms for Solving Linear Systems ............................................................................................................... 219
Chau-Jy Lin, Muh-CherngWu and Chih-Han Lin
4. Dynamic Load Balancing for Sorting Operation in Parallel Databases ................................................................................ 226
Yu-lung Lo, Shiou-jiuan Chen, Yu-chen Huang
5. An Efficient Parallel Scheme for Run-Time Scheduling .................................................................................................... 234
Tsung-Chuan Huang and Po-Hsueh Hsu