Page 73 - untitled

ࢱ᝔؁

Hsu, Tsan-sheng ޼Ӻᔊʧ Research Description
Research Description
޼Ӻᔊʧ
My current work concerns graph theory, the de- for interesting problems and designing efficient imple-
Ңͦۃٙ޼ӺʈЪdഹࠠίྡሞਿᓾ׌ሯʿ޴
sign, analysis, implementation and performance evalu- mentations to solve real-world applications. We are
ᗫᏐٙ͜޼ӺeစၑجٙணࠇeʱؓeྼЪၾࣖଟ ation of algorithms, and massive data computation and interested in both sequential, parallel and distributed
management. algorithms.
൙Пձ̶ඎ༟ࣘٙ༶ၑၾ၍ଣf
Graph theory: Massive data computation and management:
ίྡሞ˙ࠦd଺הޫٝྡ̙˸ܔᅼԨ༆Ӕ஢
Graphs model many important applications and With the rapid development of computer and
εྼყᏐ͜ਪᕚdϾ˲ɰ݊੽ԫܘεଣሞ޼Ӻٙʈ
are also tools to solve many other theoretical problems. communication technology, it has become much easier
ՈfҢࡁஷ੬΋͟ਿᓾྡሞ׌ሯٙ޼Ӻഹ˓d್ܝ We often start with probing fundamental theoretical to access or store massive amounts of data electronical- Research Fellows
problems such as the structures of graphs with certain ly. We are interested in the research problems concern-
ᔟ͟อ׌ሯٙ೯ତdணࠇ৷ࣖଟစၑdΎආɓӉઞ
properties. With these properties, we then usually de- ing efficient usage of massive data which include data
ীଣሞ߉ॎܝd̙ঐϞٙᏐ͜ᄆ࠽fᑘԷϾԊdତ sign efficient algorithms and solve applications. One privacy and computer Chinese chess. In data privacy,
example we are working on is the graph connectivity there seems to be a problem in mining massive on-line
චݬ޼Ӻሙᕚʘɓމၣ༩ᄣ੶ਪᕚfίϤҢࡁซࠅ
augmentation problem. In this problem, a minimum data for the public goods for fear of privacy leakage.
ίɓତπٙྡʕ̋ɝ௰ˇٙᗙdԴ੻ྡɪٙஹટܓ set of edges are required to add to a graph such that In view of this, we are developing formal models for
the connectivity of the resulting graph increases. This privacy protection and pricing mechanisms for privacy
ᄣ৷fவɓࡈਪᕚଣሞɪٙ߉ॎd̙˸͜˸༆Ӕ̍ problem has applications on many problems, such as leakage. We also wish to find efficient algorithms for
Research Fellows
ਿ ͉ ༟ ࣘ
ਿ
༟
͉
ࣘ
ўணࠇ̙ቦၣ༩e୕ࠇڌࣸڭ੗ʿᖭႡ̻ࠦྡίʫ the design of reliable networks, the security of statisti- checking and preventing privacy leakage. In computer
cal tables and the drawing of planar graphs. Chinese chess, we study memory-efficient algorithms
ٙ஢εᏐ͜f
for constructing huge endgame database, efficient
ᔖcc၈j޼ӺࡰResearch Fellow Design, analysis, implementation and performance algorithms for using these databases in computer Chi-
ίစၑجٙணࠇeʱؓeྼЪձࣖଟ൙П˙ evaluation of algorithms: nese chess programs, and computer models to check
௰৷ኪዝj Ph.D., Computer Sciences, University ࠦdစၑجމࠇၑዚ߅ኪٙࣨːfҢࡁϞጳሳආБ Chinese chess tie-breaking rules. It is worth while not-
of Texas at Austin (1993) Algorithm is one of the cores of computer sci- ing that our researches in massive data often benefits
ձစၑج޴ᗫٙהϞᄴࠦ޼ӺfՉʕ̍ўணࠇϞࣖ ences. We are interested in all aspects of researches from results obtained from our studies in graph theory
ཥcc༑j+886-2-2788-3799 ext. 1701 ଟٙစၑجʿՉʱؓe༆ӔྼყᏐ͜ਪᕚٙစၑج in algorithms which include finding new algorithms and algorithm.
ෂccॆj+886-2-2782-4814 ྼЪfҢࡁ࿁ృҏe̻Бձʱ౳စၑجٙ޼ӺேϞ
Selected Publications
Selected Publications
ཥɿڦᇌjtshsu@iis.sinica.edu.tw ጳሳf
1. Tsan-sheng Hsu and Vijaya Ramachandran, A linear time algorithm for tri- 13. Tsan-sheng Hsu, On four-connecting a triconnected graph, Journal of Algo-
ၣccࠫj http://www.iis.sinica.edu.tw/pages/tshsu ί̶ඎ༟ࣘٙ༶ၑၾ၍ଣ˙ࠦd͟׵ၣ༩ʿཥ connectivity augmentation, Proc. 32th Annual IEEE Symp. on Foundations rithms, volume 35, pages 202-234, 2000.
of Computer Science (FOCS), pages 548-559, 1991. 14. Tsan-sheng Hsu, Joseph C. Lee, Dian Rae Lopez and William A. Royce,

໘ࠇၑձᎷπҦஔٙ˚อ˜׸dϞ൳Ը൳ɽඎٙ༟ 2. Tsan-sheng Hsu and Vijaya Ramachandran, On finding a smallest augmen- Task allocation on a network of processors, IEEE Transactions on Comput-
tation to biconnect a graph, SIAM J. on Computing, Vol. 22, pages 889-912, ers, volume 49, number 12, pages 1339-1353, 2000.
• Deputy Director, Institute of Information Science, ৃ̙˸ᇞɪ՟੻dνОഛ͜வԬ̶ඎ༟ࣘϓމ௰อ 3. 1993. 15. Tsan-sheng Hsu, Churn-Jung Liau and Da-Wai Wang, A logical model for
privacy protection, Proc. Information Security Conference (ISC), Springer-
Tsan-sheng Hsu, Vijaya Ramachandran, and Nathaniel Dean, Implementa-
Academia Sinica (August 2002-June 2004) ٙ޼Ӻሙᕚfତචݬ޼Ӻሙᕚ̍ў༟ࣘᒯӷڭᚐʿ tion of parallel graph algorithms on the MasPar, DIMACS Series in Discrete 16. Verlag LNCS# 2200, pages 110-124, 2001.
Tsan-sheng Hsu, Churn-Jung Liau, Da-Wai Wang and Jeremy K.-P. Chen,
Mathematics and Theoretical Computer Science, volume 15, pages 165-198,
American Mathematical Society, 1994. Quantifying privacy leakage through answering database queries, Proc.
• Associate Research Fellow, Institute of Information ཥ໘൥ಒfίᒯӷڭᚐɪd͟׵߅Ҧ˚อ˜ମdɽ 4. Tsan-sheng Hsu and Vijaya Ramachandran, Efficient massively parallel 5th Information Security Conference (ISC), Springer-Verlag LNCS# 2433,
implementation of some combinatorial algorithms, Theoretical Computer pages 162-175, 2002.
Science, Academia Sinica (1997-2003) ඎ༟ࣘ˸ཥɿ˙όᎷπd̙˸Ҟ஺՟͜fᒱ್کл Science, volume 162, pages 297-322, 1996. 17. Tsan-sheng Hsu, Simpler and faster biconnectivity augmentation, Journal of
5. Tsan-sheng Hsu and Dian Rae Lopez, Bounds and algorithms for a practical Algorithms, volume 45, number 1, pages 55-71, 2002.

• Assistant Research Fellow, Institute of Information Шପ͛஢εᒯӷރᚣٙဲᅇfމəίʮ଺лूձࡈ task allocation model, Proc. 7th International Symposium on Algorithms 18. Tsan-sheng Hsu and Ping-Yi Liu, Verification of endgame databases, Inter-
and Computation (ISAAC), pages 397-406, 1996. national Computer Game Association (ICGA) Journal, volume 25, number 3,
Science, Academia Sinica (1993-1997) ɛᒯӷவՇᗭʕ՟੻̻ፅҢࡁͦۃٙ޼Ӻࠠᓃίண 6. Tsan-sheng Hsu and Ming-Yang Kao, Optimal augmentation for bipartite pages 132-144, 2002.
componentwise biconnectivity in linear time, Proc. 7th International Sym- 19. Yu-cheng Chiang, Tsan-sheng Hsu, Sun Kuo, Churn-Jung Liau and Dai-Wei

• Ph.D., Computer Sciences, University of Texas at ࠇਿ͉ٙଣሞݖ࿴dҎૐঐၚᆽ່֛ٙᒯӷdɰҎ posium on Algorithms and Computation (ISAAC), pages 213-222, 1996. Wang, Preserving confidentiality when sharing medical database with the
7. Tsan-sheng Hsu, Vijaya Ramachandran, and Nathaniel Dean, Parallel imple- Cellsecu system, International Journal of Medical Informatics, volume 71,
Austin (1993) ૐঐ˸ࠇᄆٙ˙όীሞᒯӷٙᄆ࠽f௰ܝҎૐঐ೯ mentation of algorithms for finding connected components, DIMACS Series pages 17-23, 2003.

in Discrete Mathematics and Theoretical Computer Science, volume 30, 20. Da-Wai Wang, Churn-Jung Liau and Tsan-sheng Hsu, Medical privacy
࢝Ҟ஺ٙစၑجᏨݟʮක༟ࣘʕ̙ঐٙᒯӷރဍʿ pages 23-41, American Mathematical Society, 1997. protection based on granular computing, Artificial Intelligence in Medicine

• M.S., Computer Sciences, University of Texas at 8. Lisa Hollermann, Tsan-sheng Hsu, Dian Rae Lopez, and Keith Vertanen, (AIM), volume 32, number 2, pages 137-149, 2004.
Austin (1990) ணࠇ໾હણ݄f̤ɓࡈ޼Ӻሙᕚۆ݊ཥ໘൥ಒfவ Scheduling problems in a practical allocation model, Journal of Combinato- 21. Yi-Ting Chiang, Da-Wei Wang, Churn-Jung Liau and Tsan-sheng Hsu,
rial Optimization, volume 1, number 2, Pages 129-149, 1997. Secrecy of two-party secure computation, Proc. 19th Annual IFIP WG 11.3
ܼ̍νОίাኳ᜗ʔԑًٙرɨdҞ஺ପ̶͛ඎ൥ 9. Tsan-sheng Hsu and Ming-Yang Kao, Security problems for statistical data- Working Conference on Data and Applications Security, Springer-Verlag
• B.S., Computer Science and Information Engineer- bases with general cell suppressions, Proc. 9th International Conference on LNCS#3654, pages 114-123, 2005.
ing, National Taiwan University (1985) ಒಞ҅༟ࣘࢫeνОίཥ໘൥ಒ೻όϞࣖଟԴ̶͜ Scientifi c and Statistical Database Management (SSDBM), pages 155-164, 22. Tsan-sheng Hsu, Kuo-Hui Tsai, Da-Wei Wang and D.T. Lee, Two variations
of the minimum Steiner problem, Journal of Combinatorial Optimization,
1997.
ඎ൥ಒಞ҅༟ࣘࢫeʿνОл͜ཥ໘೻όႾпᏨ᜕ 10. Tsan-sheng Hsu and Ming-Yang Kao, A unifying augmentation algorithm volume 9, pages 101-120, 2005.
• Academia Sinica Research Award for Junior Re- for two-edge connectivity and biconnectivity, Journal of Combinatorial 23. Tsan-sheng Hsu and Ming-Yang Kao, Optimal augmentation for bipartite
search Investigators (2003) ൥ಒಒ஝f 11. Optimization, volume 2, pages 237-256, 1998. componentwise biconnectivity in linear time, SIAM Journal on Discrete
Tsan-sheng Hsu and Dian Rae Lopez, Executing divisible jobs on a network
Mathematics, volume 19, number 2, pages 345-362, 2005.
with a fixed number of processors (extended abstract), Proc. 4th Interna- 24. Ping-hsun Wu, Ping-Yi Liu and Tsan-sheng Hsu, An external-memory retro-

࠽੻ءจٙ݊dҢࡁίྡሞʿစၑجٙਿᓾଣ tional Computing and Combinatorics Conf. (COCOON), pages 241-250, grade analysis algorithm, Proc. 4th International Conference on Computers
1998. and Games (CG), Springer-Verlag LNCS#3846, pages 145-160, 2006.
ሞ޼Ӻϓ؈d੬੬ϓމ̶ඎ༟ࣘ޼Ӻٙϓ̌ᗫᒟf 12. Fred S. Annexstein, Kenneth A. Berman, Tsan-sheng Hsu and Ram Swami- 25. Cho-chin Lin, Da-Wei Wang and Tsan-sheng Hsu, Bounds on the client-
server incremental computing, IEICE Trans. Fundamentals, 2006, to appear.
nathan, A multi-tree generating routing scheme using acyclic orientations,
Theoretical Computer Science, volume 240, number 2, pages 487-494,
2000.
62 63