離散專題 (2010 Spring)



邀請演講時間一般為 1:30-2:30

同學每一種顏色最多選擇一篇文章報告.

每一次報告 30 分鐘, 含 5 分鐘背景介紹, 5 分鐘主要結果的陳述, 10 分鐘證明的大綱, 5分鐘心得及可繼續做的問題, 5 分鐘回答問題(Survey 文章例外). 兩人合作報告的論文, 內容請自行協調劃分.

請 e-mail 翁志文老師 weng@math.nctu.edu.tw 你要報告的論文


先後

論文題目

報告人
3/1      From Classical Group Testing to Pooling Design 陳宏賓
3/8       A COMBINATORIAL PROOF OF THE CYCLIC SIEVING PHENOMENON FOR FACES OF COXETERHEDRA        投影片 傅東山
3/15              Lagrange interpolation formula for finite fields and its application in coding theory張耀祖
3/22  Hong-Bin Chen , Frank K. Hwang, A survey on nonadaptive group testing algorithms through the angle of decoding, J Comb Optim (2008) 15: 49–59
  M.T. Thai, D. MacCallum, P. Deng and W. Wu, Decoding algorithms in pooling designs with inhibitors and error-tolerance, Int. J. Bioinformatics Research and Applications, Vol. 3, No. 2 (2007) 145-152
  Hiroaki Uehara, A positive detecting algorithm for DNA library screening based on CCCP, 数理解析研究所講究録1465 巻2006 年138-150
洪湧昇
蔡詩妤
楊嘉勝
3/29  Piotr Indyk, Hung Q. Ngo, Atri Rudra, Efficiently Decodable Non-adaptive Group Testing, to appear in proceedings of The 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 10). January 2010. (2 人合作分兩次報告, 有機率方法 )
 Hong-Bin Chen, Hung-Lin Fu, Frank K. Hwang, An upper bound of the number of tests in pooling designs for the error-tolerant complex model, Optimization Letters (2008) 2:425–431
李權益
徐瑩晏
施智懷
4/12 YONGXI CHENG and DING-ZHU DU, Efficient Constructions of Disjunct Matrices with Applications to DNA Library Screening, JOURNAL OF COMPUTATIONAL BIOLOGY, Volume 14, Number 9, 2007, Pp. 1208–1216
Hung-Lin Fu, F.K. Hwang, A novel use of t-packings to construct d-disjunct matrices, Discrete Applied Mathematics 154 (2006) 1759 – 1762
 My T. Thai, Taieb Znati, On the complexity and approximation of non-unique probe selection using d-disjunct matrix, J Comb Optim (2009) 17: 45–53
蔡詩妤
施政成
李權益
4/19 YONGXI CHENG and DING-ZHU DU, New Constructions of One- and Two-Stage Pooling Designs, JOURNAL OF COMPUTATIONAL BIOLOGY, Volume 15, Number 2, 2008, Pp. 195–205
 Yongxi Cheng, Ding-Zhu Du, Guohui Lin, On the upper bounds of the minimum number of rows of disjunct matrices, Optim Lett (2009) 3:297–302
Vladimir D. Tonchev, Steiner systems for two-stage disjunctive testing, J Comb Optim (2008) 15: 1–6
李光祥
楊嘉勝
呂惠娟
4/26  Hong Gao, F. K. Hwang, My T. Thai, WeiliWu, Taieb Znati, Construction of d(H)-disjunct matrix for group testing in hypergraphs, J Comb Optim (2006) 12: 297-301
 Annalisa De Bonis, New combinatorial structures with applications to efficient group testing with inhibitors, J Comb Optim (2008) 15: 77–94 (2 人合作分兩次報告)
呂惠娟
李光祥
邱鈺傑
5/3  Morgan A. Bishop, Anthony J. Macula, Thomas E. Renz, Vladimir V. Ufimtsev, Hypothesis group testing for disjoint pairs, J Comb Optim (2008) 15: 7–16
  P. Damaschke, Threshold Group Testing, R. Ahlswede et al. (Eds.): Information Transfer and Combinatorics, LNCS 4123, pp. 707–718, 2006.
Jun Guo, YuexuanWang, Suogang Gao, Jiangchen Yu, WeiliWu, Constructing error-correcting pooling designs with symplectic space, J Comb Optim (2009)
蔡詩妤
洪湧昇
施智懷
5/10 Edwin R. van Dam, Willem H. Haemers, Developments on spectral characterizations of graphs, Discrete Mathematics 309 (2009) 576-586 (2 人合作分兩次報告 )
Zhifu You, Bolian Liu, The minimum Laplacian spread of unicyclic graphs, Linear Algebra and its Applications 432 (2010) 499–504
徐瑩晏
何恭毅
呂惠娟
5/17  Mikhail Belkin, Partha Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation, Neural Computation 15, 1373–1396 (2003)  (2 人合作分兩次報告 )
 Peng Jia, Junsong Yin, Xinsheng Huang, Dewen Hua, Incremental Laplacian eigenmaps by preserving adjacent information between data points, Pattern Recognition Letters 30 (2009) 1457–1463 
邱鈺傑
李忠逵
何恭毅
5/24  Steve Kirkland, Constructably Laplacian integral graphs, Linear Algebra and its Applications 423 (2007) 3–21 (2 人合作分兩次報告 )
 Jianxi Li,Wai Chee Shiu,Wai Hong Chan, The Laplacian spectral radius of some graphs, Linear Algebra and its Applications 431 (2009) 99–103
楊嘉勝
洪湧昇
施政成
5/31  Jianxi Li,Wai Chee Shiu,Wai Hong Chan, Some results on the Laplacian eigenvalues of unicyclic graphs, Linear Algebra and its Applications 430 (2009) 2080–2093 (2 人合作分兩次報告)
 Carla Silva Oliveira, Leonardo Silva de Lima, Nair Maria Maia de Abreu, Pierre Hansen, Bounds on the index of the signless Laplacian of a graph, Discrete Applied Mathematics (2009) doi:10.1016/j.dam.2009.06.023
邱鈺傑
施智懷
李忠逵




Applications



Hong-Bin Chena, Yongxi Chengb, Qian Hec, Chongchong Zhong, Transforming an error-tolerant separable matrix to an error-tolerant
disjunct matrix, Discrete Applied Mathematics


 H.B. Chen, D.Z. Du, F.K. Hwang, An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening,
superimposed codes and secure key distribution, J Comb Optim (2007) 14: 121–129


 H. B. Chen, F. K. Hwang and C. M. Li, BOUNDING THE NUMBER OF COLUMNS WHICH APPEAR ONLY IN POSITIVE POOLS, TAIWANESE JOURNAL OF MATHEMATICS Vol. 10, No. 4, pp. 927-932, June 2006

 Ferdinando Cicalese and Jose Augusto Amgarten Quitzau, 2-Stage Fault Tolerant Interval Group Testing, T. Tokuyama (Ed.): ISAAC 2007, LNCS 4835, pp. 858–868, 2007.

 Hong-Bin Chen, Frank K. Hwang, Exploring the missing link among d-separable, d-separable and d-disjunct matrices, Discrete Applied Mathematics 155 (2007) 662 – 664


Algorithms



Constructions or Characterizations



Geng-sheng Zhang, Xiao-lei Sun, Bo-li Li, Error-correcting pooling designs associated with the dual space of unitary space and ratio efficiency comparison, J Comb Optim (2009) 18: 51–63

Ping Deng, F.K. Hwang,WeiliWu, David MacCallum, FengWang, Taieb Znati, Improved construction for pooling design, J Comb Optim (2008) 15: 123–126



Jizhu Nan Jun Guo, New error-correcting pooling designs associated with finite vector spaces, J Comb Optim

V. M. Sidelnikov and O. Yu. Prikhodov, On the Construction of (w, r) Cover-Free Codes, Problems of Information Transmission, 2009, Vol. 45, No. 1, pp. 32–36

 Jun Guo, Pooling designs associated with unitary space and ratio efficiency comparison, J Comb Optim



Geng-Sheng Zhang, Yu-Qin Yang, The arrangement of subspaces in the orthogonal spaces and tighter analysis of an error-tolerant pooling design, J Comb Optim

 Zengti Li, Suogang Gao, Hongjie Du, Feng Zou, WeiliWu, Two constructions of new error-correcting pooling designs from orthogonal spaces over a finite field of characteristic 2, J Comb Optim

 Xinlu Zhang, Jun Guo, Suogang Gao, Two new error-correcting pooling designs from d-bounded distance-regular graphs, J Comb Optim (2009) 17: 339–345


Bounds


Kinkar Ch. Das, R.B. Bapat, A sharp upper bound on the largest Laplacian eigenvalue of weighted graphs, Linear Algebra and its Applications 409 (2005) 153–165