Maw-Shang Chang (張貿翔)

  Professor
  Department of Computer Science and Information Engineering
  National Chung Cheng University
  Chiayi 621, Taiwan

  Tel: +886 5 272-0411 ext. 33106
  Fax:+886 5 272-0859
  Email: mschang@cs.ccu.edu.tw

 

Maw-Shang Chang received his Ph.D. degree from the Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, in 1990. He has been with the Department of Computer Science and Information Engineering, National Chung Cheng University since Feb. 1990. His research interests include algorithmic graph theory and computational molecular biology.

 

 

[A] Refereed Papers

 

1.     Maw-Shang Chang, N. F. Huang, and C. Y. Tang, 1990:

An optimal algorithm for constructing oriented Voronoi diagrams and geographic neighborhood graphs, Information Processing Letters 35 (1990) pp.255-260.

 

2.     Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1991:

20-relative neighborhood graphs are Hamiltonian, J. of Graph Theory 15 (1991) 543-547.

 

3.     Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1992:

Solving the Euclidean bottleneck matching problem by k-relative neighborhood graph, Algorithmica 8 (1992) 177-194.

 

4.     Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1992:

Solving the Euclidean bottleneck biconnected edge subgraph problem by 2relative neighborhood graphs, Discrete Applied Mathematics 39 (1992) 1-12.

 

5.     S. L. Peng and Maw-Shang Chang,1992:

A simple and linear time algorithm for domatic partition problem on strongly chordal graphs, Information Processing Letters 43 (1992) 297-300.

 

6.     Maw-Shang Chang and F. H. Wang, 1992:

Efficient algorithms for maximum weighted clique and independent set problems on permutation graphs, Information Processing Letters 43 (1992) 293-295.

 

7.     Maw-Shang Chang and Y. C. Liu, 1993:

Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, Information Processing Letters 48 (1993) 205-210.

 

8.     Maw-Shang Chang and Y. C. Liu, 1994:

Polynomial algorithms for weighted perfect domination problems on interval and circular-arc graphs, J. of Information Science and Engineering 10 (1994) 549-568.

 

9.     A. Srinivasan, It. Madhukar, P. Nagavamsi, C. Pandu Rangan, and Maw-Shang Chang, 1995:

Edge domination on bipartite permutation graphs and cotriangulated graphs, Information Processing Letters 56 (1995) 165-171.

 

10.   Maw-Shang Chang, Y. H Chen, G. J. Chang, and J. H. Yan, 1996:

Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Discrete Applied Mathematics 66 (1996) 189-203.

 

11.   Y. D. Liang and Maw-Shang Chang, 1997:

Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs, Acta Informatica 34 (1997) 337-346.

 

12.   Maw-Shang Chang and Chung-Chang Hsu, 1997:

On minimum intersection of two minimum dominating sets of interval graphs, Discrete Applied Mathematics 78 (1997) 41-50.

 

13.   Maw-Shang Chang, 1997:

Weighted domination of cocomparability graphs, Discrete Applied Mathematics 80 (1997) 135-148.

 

14.      Maw-Shang Chang, P. Nagavamsi, and C. Pandu Rangan, 1998:

Weighted irredundance of interval graphs, Information Processing Letters 66 (1998) 65-70.

 

15.   Maw-Shang Chang, 1998:

Efficient algorithms for the weighted domination problem on interval and circular-arc graphs, SIAM J. on Computing 27 (1998) 1671-1694.

 

16.   Maw-Shang Chang, S. L. Peng, and J. L. Liaw, 1999:

Deferred-Query: An efficient approach for some problems on interval graphs, Networks 34 (1999) 1-10.

 

17.         Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, G. J. Chang, and C. K. Wong, 2001:

The Kr-packing problem, Computing 66 (2001) 79-89.

 

18.        G. J. Chang, Maw-Shang Chang, Shaur-Ching Wu and Hong-Gwa Yeh 2002:

Domination in distance-hereditary graphs, Discrete Applied Mathematics 116 (2002) 103-113.

 

19.        Ruo-Wei Hung, Shaur-Ching Wu, and Maw-Shang Chang 2003:

Hamiltonian cycle problem on distance-hereditary graphs, J. of Information Science and Engineering 19 (2003) 827-838.

 

20.        Ruo-Wei Hung and Maw-Shang Chang 2004:

A linear algorithm for the connected domination problem on circular-arc graphs, Discussiones Mathematicae Graph Theory, 24 (2004) 137-146.

 

21.        Maw-Shang Chang, Chin-Hua Lin, and Chuan-Min Lee 2004:

New upper bounds on feedback vertex numbers in butterflies, Information Processing Letters 90 (2004) 279-285.

　

22.   Chuan-Min Lee, Ling-Ju Hung, Maw-Shang Chang, Chia-Ben Shen, and Chuan-Yi Tang 2005:

An improved algorithm for the maximum agreement subtree problem, Information Processing Letters 94 (2005) 211-216.

　

23.        Ruo-Wei Hung and Maw-Shang Chang 2005:

        Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Theoretical Computer Science, 341 (2005) 411-440.

 

24.   Ruo-Wei Hung and Maw-Shang Chang 2006:

       Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Discrete Applied Mathematics 154 (2006) 76-105.

 

25.       Chuan-Min Lee and Maw-Shang Chang 2006:

Distance-hereditary graphs are clique-perfect, Discrete Applied Mathematics 154 (2006) 525-536.

 

26.        Ruo-Wei Hung and Maw-Shang Chang 2007:

Finding a minimum path cover of a distance-hereditary graph in polynomial time, Discrete Applied Mathematics 155 (2007) 2242-2256.

 

27.        Chuan-Min Lee and Maw-Shang Chang 2007:

Variations of Y-dominating functions on graphs, Discrete Mathematics, In Press, Corrected Proof, Available online 1 October 2007.

 

28.        David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu and Sheng-Lung Peng 2008:

Partitioned probe comparability graphs, Theoretical Computer Science, In Press, Accepted Manuscript,  Available online 2 February 2008.

 

　

　

[B] Conference Papers

 

1.    Maw-Shang Chang and R. C. T. Lee, 1983:

Two algorithms of the closest pair problems suitable for VLSI system, Proceedings of Symposium on VLSI Technology, System and Applications, Taipei, R.O.C., (1983) 231-234.

 

2.    Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1988:

The Euclidean bottleneck matching problem, Proceedings of National Computer Symposium, Taipei, R.O.C., (1988) 776-781.

 

3.    Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1989:

Solving the Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs, Proceedings of National Computer Symposium, Taipei, R.O.C., (1989) 53-58.

 

4.    Maw-Shang Chang, N. F. Huang, and C. Y. Tang, 1989:

An optimal algorithm for constructing oriented Voronoi diagrams and geographic neighborhood graphs, Proceedings of International Computer Symposium, Taipei, R.O.C., (1989) 102-105.

 

5.    Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1990:

20-Relative neighborhood graphs are Hamiltonian, Algorithms, Lecture Notes in Computer Science, Vol 450, Edited by T. Asano et al., Springer-Verlag, (1990) 53-65.

 

6.    Maw-Shang Chang, C. Y. Tang, and R. C. T. Lee, 1991:

A unified approach for solving bottleneck k-bipartition problem, Proceedings of 1991 ACM Computer Science Conference, San Antonio, Texas, IJSA (1991) 39-47.

 

7.    Maw-Shang Chang and R. W. Hung, 1991:

An efficient strategy using linked blocks for multiple stacks manipulation, Proceedings of National Computer Symposium, Taipei, R.O.C., (1991) 37-42.

 

8.    S. L. Peng and Maw-Shang Chang, 1991:

A new approach for domatic number problem on interval graphs, Proceedings of International Computer Symposium, Taipei, R.O.C., (1991) 236-241.

 

9.    Maw-Shang Chang, 1992:

Efficient algorithms for domination problems on interval and circular-are graphs, Algorithms, Software, Architecture (Proceedings of IFIP 12th computer congress), Edited by J. Van Leeuwen, Elsevier Science Publishers B. V. (1992) 402-408.

 

10.  Maw-Shang Chang, S. L. Peng, and J. L. Liaw, 1993:

Deferred-query -- An efficient approach for problems on interval and circular-arc graphs, Lecture Notes in Computer Science, Vol. 709 (Proceedings of WADS‘93), Edited by F. Dehne et al., Springer-Verlag, (1993) 222-233.

 

11.   Maw-Shang Chang, P. Nagavamsi, and C. Pandu Rangan, 1994:

Weighted irredundancy in interval graphs, Lecture Notes in Computer Science (Proceeding of ISAAC‘94) , Springer-Verlag, (1994).

 

12.  Maw-Shang Chang, 1995:

Weighted domination of cocomparability graphs, Lecture Notes in Computer Science Vol. 1004 (Proceedings of ISAAC'95), Springer-Verlag, (1995) 122-131.

 

13.  Maw-Shang Chang, 1996:

Algorithms for maximum matching and minimum fill-in of chordal graphs, Lecture Notes in Computer Science Vol. 1178 (Proceedings of ISAAC'96), Springer-Verlag, (1996) 146-155.

 

14.  Maw-Shang Chang, Sun-yuan Hsieh, and Gen-Huey Chen, 1997:

Dynamic programming on distance-hereditary graphs, Lecture Notes in Computer Science Vol. 1350 (Proceedings of ISAAC'97), Springer-Verlag, (1997) 344-353.

 

15.  Maw-Shang Chang and Rue-Lin Yang, 1998:

Edge Domination of Distance-Hereditary Graphs, Proceedings of Workshop on Algorithms, International Computer Symposium, Taiwan, R.O.C., (1998) 112-115.

 

16.  Y. Daniel Liang and Maw-Shang Chang, 1998:

Parallel Algorithms for the Hamiltonian Circuit Problem in Convex Bipartite Graphs and Circular Convex Bipartite Graphs, Proceedings of Workshop on Algorithms, International Computer Symposium, Taiwan, R.O.C., (1998) 36-43.

　

17.   V. Guruswami, C. Pandu Rangan, Maw-Shang Chang, G. J. Chang and C. K. Wong, 1998:

The vertex-disjoint triangles problem, Proceedings of WG'98, Smolenice Castle, Slovakia, June 1998.

18.        Maw-Shang Chang, Shaur-Ching Wu, Gerard J. Chang, Hong-Gwa Yeh, 2000:

Hamiltonian Problems on Ptolemaic Graphs, Proceedings of Workshop on Algorithms and Theory of Computation, International Computer Symposium, Chiayi, Taiwan, R.O.C., (2000) 27-34

19.  Maw-Shang Chang, Ton Kloks, and Chuan-Min Lee, 2001:

Maximum Clique Transversals, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2204, Springer, Proceedings of the 27th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Boltenhagen, Germany (2001), 32-43.

　

20.  Maw-Shang Chang and Haiko Muller 2001:

On the Tree-Degree of Graphs, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2204, Springer, Proceedings of the 27th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Boltenhagen, Germany (2001), 44-54.

　

21.  Chuan-Min. Lee, Ling-Ju Hung, Maw-Shang Chang and Chuan-Yi Tang 2004:

An improved algorithm for the maximum agreement subtree problem, Proceedings of the 4th IEEE Symposium on BioInformatics and BioEngineering (BIBE 2004), Taichung, Taiwan, R. O. C.  (2004), 533-536.

 

22.  Hsin-Fu Chen and Maw-Shang Chang 2004:

An efficient exact algorithm for the minimum  ultrametric tree problem, Lecture Notes in Computer Science Vol. 3341 (Proceedings of ISAAC 2004), Springer-Verlag, (2004) 278-289.

　

23.        Maw-Shang Chang, Ton Kloks, Dieter Kratsch, Jiping Liu and Sheng-Lung Peng 2005:

        On the recognition of probe graphs of some self-complementary classes of perfect graphs, Lecture Notes in Computer Science Vol. 3595 (Proceedings of COCOON 2005), Springer-Verlag, (2005) 808-817.

 

24.   David B. Chandler, Maw-Shang Chang, Antonius J.J. Kloks, Jiping Liu, and Sheng-Lung Peng, On probe permutation graphs (Extended Abstract), Lecture Notes in Computer Science Vol. 3959 (Proceedings of TAMC 2006), Springer-Verlag, (2006) 494-504.

 

25.   David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng, Recognition of probe cographs and partitioned probe distance hereditary graphs, Lecture Notes in Computer Science Vol. 4041 (Proceedings of AAIM 2006), Springer-Verlag, (2006) 267-278.

 

25.       Maw-Shang Chang, Ming-Tat Ko, and Hsueh-I Lu, Linear-time algorithms for tree root problems, Lecture Notes in Computer Science Vol. 4059 (Proceedings of SWAT 2006), Springer-Verlag, (2006) 411-422.

 

26.       David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng, Partitioned probe comparability graphs, Lecture Notes in Computer Science Vol. 4271 (Proceedings of WG 2006), Springer-Verlag, (2006) 179-190.

 

　

[C] 圖書資訊相關論述：

 

1.         張貿翔 1999：

大學圖書館在網際網路之發展，網際網路與圖書館發展研討會論文集，中國圖書館學會主辦 (1999) 73-77。

 

2.         張貿翔 1999：

書目整合實務問題探討，華文書目資料庫合作發展研討會論文集，國家圖書館漢學研究中心主辦 (1999) 163-170。

 

3.         張貿翔 2001：

兩岸三地圖書館虛擬聯合目錄，第三屆海峽兩岸圖書資訊研討會--海峽兩岸資料庫/數據庫與資訊/信息服務交流與合作--論文集，中華圖書資訊館際合作協會主辦 (2001) 97-102。

 

　

　

[D] 圖書館相關研究計畫：

 

1.         國內圖書館虛擬聯合目錄計畫(1998/7~1999/6)，教育部電算中心委託計畫，擔任主持人。

 

2.         八十八年度圖書館自動化及網路化策略推動委員會(1998/8~1999/6)，教育部電算中心委託計畫，擔任召集人。

 

3.         中文期刊聯合目錄暨館際互借管理系統建置計畫(1998/12~2000/6)，國家圖書館委託計畫，擔任主持人。