Page 99 - untitled

৵Іܩ

Ma, Tze-Heng ਿ ͉ ༟ ࣘ Research Description
ਿ ͉ ༟ ࣘ
Research Description

ᔖcc၈jਓ޼Ӻࡰ Associate Research Fellllow My current research interests mainly focus on a non-traditional approach, I have devised simpler
two areas: graph Algorithms and Chinese character and efficient algorithms on two and three vertex
௰৷ኪዝjPh.D., CS, Vanderbilt University
recognition. On graph algorithms, I§m particularly connectivity augmentation algorithms. I am trying
ཥcc༑j+886-2-2788-3799 ext. 1728 interested in graphs that have some "geometric" to extend this novel approach to more complicated
ෂccॆj+886-2-2782-4814 properties. For example, interval graph, permutation problems. With reference to Chinese character rec-

ཥɿڦᇌjmada@iis.sinica.edu.tw graph, etc. In the past, I have developed algorithms ognition, I have developed two prototypes. TLH
for recognizing several classes of graphs. These is an on-line hand writing recognition system and Research Fellows
ၣccࠫjhttp://www.iis.sinica.edu.tw/pages/mada
algorithms are either new or more efficient than the Ning is a recognition core for printed characters.
existing algorithms. I am also interested in solv- Both systems are based on the template matching
ing various combinatorial optimization problems approach instead of the more traditional structural
on these classes of graphs. To this end, I am trying analysis method. I believe, as the technology in
• Assistant Research Fellow , Institute of Information to find new properties or to take a new approach personal computer advances, that a lot of new ap-
Research Fellows
Science, Academia Sinica (1990-1997)
S to solve some old problems on various types of proaches that were not feasible in the past, deserve
Ph.D., CS, Vanderbilt University (1990), graphs. One problem I can currently focus on is the to be look at from a new standpoint.
޼Ӻᔊʧ
B.S., CSIE, National Taiwan University (1983), ޼Ӻᔊʧ
vertex connectivity augmentation problem. Using
Ңٙ޼Ӻ˙Σ˴ࠅഹࠠ׵Շࡈჯਹmྡٙစ
ၑجၾʕ˖˖οᗆйfίྡٙစၑج˙ࠦdҢ࿁׵
ɓԬ່֛׵ݔԬ¨఻О׌ሯ©ɪٙྡतйϞጳሳf
Selected Publications
Selected Publications
ˢ˙Ⴍਜගྡeરΐྡഃഃfཀ̘Ңಀணࠇ̈ɓԬ
စၑجԸ፫ᗆݔɓԬɿྡfவԬစၑجڢШ༰ࡡϞ 1. ಀ˖ኮeੵ௹ሞe৵Іܩ (2004)d዆Υ؂ਕਪ՜ሜݟӻ୕ʘࣨː 8. M. J Jou, G. J. Chang, C. Lin, and T. H. Ma, A Finiteness Theorem for
ˏᏗணࠇd਷ყᔼኪ༟ৃ޼ীึ(MIST).€਷ʫ Maximal Independent Sets, Graphs and Combinatorics 12, 321-326,
ʘ˙جҞ஺dϾ˲һঐ೯ઢ̈வԬྡٙɓԬᆑί׌
2. Wen-Hsien Tseng, Tze-Heng Ma, and Polun Chang (2004), “The 1996.
ሯfҢΝࣛɰ࿁הɓԬଡ଼Υ௰ԳʷٙਪᕚϞጳሳf Development of the Integrated Framework of the Automatic Question- 9. T. H. Ma and J. Spinrad, An 0(n2) Algorithm for 2 Chain Subgraph
naire system,” paper at Health Management Society of Taiwan (HMST). Cover Problem and Related Problems, Journal of Algorithms 17,
ΝᅵήdҢҎࡈᔟഹ޼ӺவԬྡٙ֠͊஗೯ତٙ׌
（國內） 251-268,1994.
ሯԸ༺ՑϤɓͦٙfͦۃҢ࿁ᄣ̋ྡٙᓃஹഐ׌வ 3. C. C. Jung, T. H. Ma, and Y. S. Kuo, Simplified Graph Model for User 10. T. H. Ma and J. Spinrad, An 0(n2) Algorithm for Undirected Split De-

ࡈਪᕚਂəɓԬ޼ӺfҢ೯ତəɓࡈอٙ˙࿁ɚʿ Interface Constraints, IEICE Transactions Information and Systems, composition, Journal of Algorithms 16, 145-160, 1994.
pp.2427-2432, Novenber 2003 11. T. H. Ma, On the Threshold Dimension 2 Graphs, (presented at the 6th
ɧஹഐ€̋˸௰ˇٙᗙҬՑəᔊఊʿϞࣖٙစၑ
4. W. L. Hsu and T. H. Ma. Substitution Decomposition on Chordal SIAM Conference on Discrete Mathematics, Vancouver, 1992). Sub-
جfҎૐ͊Ըঐਗ਼ତϞٙഐ؈ᓒ࢝Ցһ৷ٙஹഐ׌ Graphs and Applications, SIAM J. Comput, 28, 1004-1020, 1999. mitted to SIAM J. Discrete Math.

ɪfίʕ˖˖οᗆй˙ࠦdҢ೯࢝̈əՇࢁࡡۨӻ 5. C.W. Yu, G. H. Chen, and T. H. Ma, On the Complexity of the k-chain 12. J. M. Ho, M. T. Ko, T. H. Ma, and T. Y. Sung, Algorithms for Rec-
subgraph cover problem, Theoretical Computer Science 205, 85-98, tilinear Optimal Multicast Tree Problem, Proc. Third International
୕fୋɓࡈ݊уࣛʕʘ˓ᄳ፩ɝӻ୕ḍਂɺथ 1998. Symposium on Algorithms and Computation, 1992, Lecture Notes in
૩fୋɚࡈ݊ʕ˖ΙՏ᜗፫ᗆӻ୕ḍਂᕿྐྵfவ 6. T. H. Ma, On the Biconnectivity Augmentation Problem, CTS Work- Computer Science 650, 106-115.
shop on Combinatorics and Algorithms, 66-73, 1998. 13. T. H. Ma and J. Spinrad, Cycle-free Partial Orders and Chordal Com-
Շࡈӻ୕ே݊ܔͭίᅵ͉ˢ࿁ٙਿᓾɪiϞй׵༰
7. C. F. Tsai and T. H. Ma, Online Handwriting Recognition by Template parability Graphs, Order 8, 175-183, 1991.
੬Ԉٙഐ࿴ʱؓ˙جfҢ޴ڦᎇഹࡈɛཥ໘஺ܓٙ Matching, Proc. National Computer Symposium, B39-B44, 1997. 14. T. H. Ma and J. Spinrad, Transitive Closure for Restricted Classes of
Ҟ஺೯࢝d஢ε˸ۃʔ̙ঐᎻ༊ٙ˙Σdே࠽੻ࠠ Partial Orders, Order 8, 46-61, 1991.
อᏨൖf

90 91