王炳豐 (Biing-Feng Wang)

教授
  • 國立台灣大學博士
  • 研究領域: 演算法設計與分析、平行計算
Professor
  • Department of Computer Science, National Tsing Hua University
  • Ph.D., National Taiwan University
  • Research Field: Algorithm design, Parallel processing
Contact Info
  • E-Mail: bfwang@cs.nthu.edu.tw
  • Office: Room 548, EECS building
  • Tel: (886) 3574-2805

Curriculum Vitae

學歷
國立臺灣大學資訊工程所 (博士)
1988/9 ~ 1991/6
國立交通大學資訊科學系 (學士)
1984/9 ~ 1988/6
經歷
清華大學資訊系教授
1999/8 ~ present
清華大學資訊系系主任
2003/8 ~ 2006/7
清華大學計算機中心系統組組長
1998/1 ~ 2000/6
清華大學資訊系副教授
1993/8 ~ 1999/7
經濟部主導性新產品開發計畫技術審查委員會委員
1988/7 ~ 1992/7
專長領域
演算法設計與分析 (Design and Analysis of Algorithms)
平行計算 (Parallel Computation)
榮譽
國 科 會 甲 等 研 究 獎 助, 1993 ~ 2000
清 華 大 學 傑 出 教 學 獎, 1998
清 華 大 學 新 進 人 員 研 究 獎, 1998
中 央 研 究 院 年 輕 學 者 研 究 著 作 獎, 1999
ACM 李 國 鼎 青 年 研 究 獎, 1999
ISI Citation Classic Award, 2001
國 科 會 傑 出 研 究 獎, 2002
清 華 大 學 傑 出 教 學 獎, 2003
清 華 大 學 特 聘 教 授, 2006
清 華 大 學 傑 出 教 學 獎, 2007

Publications

International Journals
[J1]
B.-F. Wang*, J.-H. Ye, and P.-J. Chen, "Efficient algorithms for the round-trip 1-center and 1-median problems," Journal of Computer and System Sciences, accepted.
[J2]
B.-F. Wang*, "A new efficient algorithm for the all sorting reversals problem with no bad components," IEEE/ACM Transactions on Computational Biology and Bioinformatics, accepted.
[J3]
J.-H. Ye and B.-F. Wang* (2015), "On the minmax regret path median problem on trees," Journal of Computer and System Sciences, vol. 81, iss. 7, pp. 1159-1170.
[J4]
B.-F. Wang*, C.-H. Lin, and I-T. Yang (2014), "Constructing a gene team tree in almost O(n lg n) time," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 11, no. 1, pp. 142-153.
[J5]
R. Benkoczi, B. K. Bhattacharya, Y. Hu, C.-H. Lin, Q. Shi, and B.-F. Wang* (2012), "Efficient algorithms for the conditional covering problem," Information and Computation, vol. 219, pp. 39-57.
[J6]
B.-F. Wang* (2012), "Output-sensitive algorithms for finding the nested common intervals of two general sequences," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 9, no. 2, pp. 548-559.
[J7]
B.-F. Wang*, C.-C. Kuo, S.-J. Liu, and C.-H. Lin (2012), "A new efficient algorithm for the gene team problem on general sequences," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 9, no. 2, pp. 330-344, 2012.
[J8]
C.-Y. Chan, H.-I Yu, W.-K. Hon, and B.-F. Wang* (2011), "Faster query algorithms for the text fingerprinting problem," Information and Computation, vol. 209, no. 7, pp. 1057-1069.
[J9]
B.-F. Wang* and C.-H. Lin (2011), "Improved algorithms for finding gene teams and constructing gene team trees," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 5, no. 5, pp. 1258-1272, 2011.
[J10]
C.-C. Yu, W.-K. Hon, and B.-F. Wang* (2011), "Improved data structures for the orthogonal range successor problem," Computational Geometry: Theory and Applications, vol. 44, iss. 3, pp. 148-158.
[J11]
C.-C. Yu, C.-H. Lin, and B.-F. Wang* (2010), "Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph," Journal of Computer and System Sciences, vol. 76, iss. 8, pp. 697-708.
[J12]
L.-P. Yeh, B.-F. Wang*, and H.-H. Su (2010), "Efficient algorithms for the problems of enumerating cuts by non-decreasing weights", Algorithmica, vol. 56, no. 3, pp. 297-312. (NSC-97-2221-E-007- 118)
[J13]
J.-J. Lin, and C.-Y. Chan, and B.-F. Wang* (2010), "Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches," Discrete Applied Mathematics, vol. 150, issue 8, pp. 943-950. (NSC-97-2221-E-007-053)
[J14]
T.-C. Lin, C.-C. Kuo, Y.-H. Hsieh, and B.-F. Wang* (2009), "Efficient algorithms for the inverse sorting problem with bound constraints under the l-norm and the hamming distance," Journal of Computer and System Sciences, vol. 75, issue 8, pp. 451-464. (NSC-97-2221-E-007-053-MY3)
[J15]
C.-Y. Chan, S.-C. Ku, C.-J. Lu, and B.-F. Wang* (2009), "Efficient algorithms for two generalized 2-median problems and the group median problem on trees," Theoretical Computer Science, vol. 410, no. 8-10, pp. 867-876. (NSC-96-2221-E-007-029)
[J16]
H.-I Yu, T.-C. Lin, and B.-F. Wang* (2008), "Improved algorithms for the minmax-regret 1-center and 1-median problems," ACM Transactions on Algorithms, vol. 4, no. 3, article no. 36. (NSC-94-2213-E-007-082, NSC- 95-2221-E-007-028)
[J17]
B.-F. Wang*, T.-C. Lin, C.-H. Lin, and S.-C. Ku (2008), "Finding the conditional location of a median path on a tree," Information and Computation, vol. 206, no. 7, pp. 828-839. (NSC-93-2213-E-007-006, NSC93-2752-E-007- 004-PAE)
[J18]
Y.-H. Hsieh, C.-C. Yu, and B.-F. Wang* (2008), "Optimal algorithms for the interval location problem with range constraints on length and average," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 5, no. 2, pp. 281-290. (EI, SCI) (NSC-94-2213-E-007-091, NSC-95-2213- E-002-029)
[J19]
H.-L. Cheng* and B.-F. Wang (2007), "On Chen and Chen's new tree inclusion algorithm," Information Processing Letters, vol. 103, no. 1, pp. 14-18. (EI, SCI)
[J20]
B.-F. Wang*, S. Peng, H.-Y. Yu, and S.-C. Ku (2006), "Efficient algorithms for a constrained k-tree core problem in a tree network," Journal of Algorithms, vol. 59, pp. 107-124. (EI, SCI) (NSC-92- 2213-E-007-006, NSC-93-2752-E-007-004-PAE)
[J21]
B.-F. Wang* (2005), "Linear time algorithms for the ring loading problem with demand splitting," Journal of Algorithms, vol. 54, pp. 45-57. (EI, SCI) (NSC-93-2213-E-007- 029)
[J22]
B.-F. Wang* (2004), "Finding r-dominating sets and p-centers of trees in parallel," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 8, pp. 687-698. (EI, SCI) (NSC-91-2213-E-007-044)
[J23]
B.-F. Wang*, J.-J. Lin, and S.-C. Ku (2004), "Efficient algorithms for the scaled indexing problem," Journal of Algorithms, vol. 52, pp. 82-100. (EI, SCI) (NSC-92-2213-E-007-021)
[J24]
S.-C. Ku, B.-F. Wang*, and, T.-K. Hung (2003), "Constructing edge-disjoint spanning trees in product networks," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 3, pp. 213-221. (EI, SCI) (NSC-90-2213-E-007-071)
[J25]
B.-F. Wang* (2002), "Finding a two-core of a tree in linear time," SIAM Journal on Discrete Mathematics, vol. 15, no. 2, pp. 193-210. (EI, SCI) (NSC-90-2213-E-007-061)
[J26]
S.-C. Ku and B.-F. Wang* (2002), "An optimal simple parallel algorithm for testing isomorphism of maximal outerplanar graphs," Journal of Parallel and Distributed Computing, vol. 62, pp. 221-227. (EI, SCI) (NSC-89-2213-E-007-017)
[J27]
B.-F. Wang*, S. C. Ku, and K.-H. Shi (2001), "Cost-optimal parallel algorithms for the tree bisector and related problems," IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, pp. 888-898. (EI, SCI) (NSC-89-2213-E-007-099)
[J28]
C.-H. Peng, B.-F. Wang*, and J.-S. Wang (2000), "Recognizing unordered depth-first search trees of an undirected graph in parallel," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 6, pp. 559-570. (EI, SCI) (NSC-84-2221-E-007-002)
[J29]
B.-F. Wang* (2000), "Tight bounds on the solutions of multidimensional divide-and-conquer maximum recurrences," Theoretical Computer Science, vol. 242, pp. 377-401. (EI, SCI) (NSC-86- 2213-E-007-042)
[J30]
B.-F. Wang* (2000), "Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network," Journal of Algorithms, vol. 34, pp. 90-108. (EI, SCI) (NSC-87-2213-E-007-066)
[J31]
B.-F. Wang*, J.-N. Tsai, Y.-C. Chuang (1999), "The lowest common ancestor problem on a tree with an unfixed root," Information Sciences, vol. 119, no. 1-2, pp.125-130. (EI, SCI)
[J32]
R. Lin, S. Olariu, J. L. Schwing, and B.-F. Wang (1999), "The mesh with hybrid buses: an efficient parallel architecture for digital geometry," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no.3, pp. 266-279. (EI, SCI) (NSC-86-2221-E-007-028)
[J33]
D.-J. Shyu, B.-F. Wang*, and C.-Y. Tang (1998), "Efficient emulations for X-trees and m-ary trees," Journal of Parallel Algorithms and Applications, vol. 13, pp. 95-116. (NSC-84-0408-E-007-006)
[J34]
B.-F. Wang* (1998), "Simulating the CRCW PRAM on reconfigurable networks," Theoretical Computer Science, vol. 205, no. 1-2, pp. 231-242. (EI, SCI) (NSC-83-0408-E-007-013)
[J35]
B.-F. Wang*, (1998), "Finding a k-tree core and a k-tree center of a tree network in parallel," IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 2, pp. 186-191. (EI, SCI) (NSC-85- 2221-E-007-021)
[J36]
B.-F. Wang* (1997), "Tighter bounds on the solution of a divide-and-conquer maximin recurrence," Journal of Algorithms, vol. 23, pp. 329-344. (EI, SCI)
[J37]
B.-F. Wang* (1996), "A better analysis of Ben-Asher's algorithm for the conditional cartesian product problem," Parallel Processing Letters, vol. 6, no. 3, pp. 331-344. (EI)
[J38]
G.-H. Chen, S. Olariu, J. L. Schwing, B.-F. Wang, and J. Zhang (1995), "Constant time tree algorithms," Journal of Parallel and Distributed Computing, vol. 26, pp. 137-150. (EI, SCI)
[J39]
G.-H. Chen and B.-F. Wang (1994), "Cost-optimal parallel algorithms for constructing B-trees," Information Sciences, vol. 81, no.1-2, pp. 55-72. (EI, SCI)
[J40]
G.-H. Chen and B.-F. Wang (1993), "Sorting and computing convex hulls on processor arrays with reconfigurable bus systems," Information Sciences, vol. 71, no. 3, pp. 191-206. (EI, SCI)
[J41]
G.-H. Chen, B.-F. Wang, and H. Li (1993), "Deriving algorithms on reconfigurable networks based on function decomposition," Theoretical Computer Science, vol. 120, pp. 215-227. (EI, SCI)
[J42]
B.-F. Wang, G.-H. Chen, and K. Park (1993), "On the set LCS and set-set LCS problems," Journal of Algorithms, vol. 14, pp. 466-477. (EI, SCI)
[J43]
G.-H. Chen, B.-F. Wang, and C.-J. Lu (1992), "On the parallel computation of the algebraic path problem," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 2, pp. 251-256. (EI, SCI)
[J44]
B.-F. Wang, C.-L. Chen, and G.-H. Chen (1991), "A simple approach to implementing multiplication with small tables," Information Processing Letters, vol. 37, no. 6, pp. 327-329. (EI, SCI)
[J45]
B.-F. Wang and G.-H. Chen (1991), "Cost-optimal parallel algorithms for constructing 2-3 trees," Journal of Parallel and Distributed Computing, vol. 11, no. 3, pp. 257-261. (EI, SCI)
[J46]
B.-F. Wang and G.-H. Chen (1990), "Two-Dimensional processor array with a reconfigurable bus system is at least as powerful as the CRCW model," Information Processing Letters, vol. 36, no. 1, pp. 31-36. (EI, SCI)
[J47]
B.-F. Wang and G.-H. Chen (1990), "Constant time algorithms for the transitive closure and some related graph problems on processor arrays with reconfigurable bus systems," IEEE Transactions on Parallel and Distributed Systems, vol. 1, no. 4, pp. 500-507. (EI, SCI)
[J48]
B.-F. Wang, G.-H. Chen, and F. C. Lin (1990), "Constant time sorting on processor arrays with reconfigurable bus systems," Information Processing Letters, vol. 34, no. 4, pp. 187-192. (EI, SCI)
Conference Proceedings
[C1]
C.-H. Li, J.-H. Ye, and B.-F. Wang, "A linear-time algorithm for the minimum degree hypergraph problem with the consecutive ones property," in Proceedings of the 19th International Computing and Combinatorics Conference (COCOON 2013), Lecture Notes in Computer Science, vol. 7936, pp. 268-279. (EI, SCI)
[C2]
B.-F. Wang and C.-H. Li (2012), "On the minimum degree hypergraph problem with subset size two and the red-blue hitting set problem with the consecutive ones property," in Proceedings of the 18th International Computing and Combinatorics Conference (COCOON 2012), Lecture Notes in Computer Science, vol. 7434, pp. 169-180. (EI, SCI)
[C3]
B.-F. Wang, J.-H. Ye, and P.-J. Chen (2012), "On the round-trip 1-center and 1-median problems," in Proceedings of Workshop on Algorithms and Computation (WALCOM 2012), 2012, Lecture Notes in Computer Science, vol. 7151, pp. 100-111. (EI, SCI)
[C4]
C.-C. Yu, B.-F. Wang, and C.-C. Kuo (2010), "Efficient indexes for the positional pattern matching problem and two related problems over small alphabets," in Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, vol. 6507, pp. 13-24. (EI, SCI)
[C5]
B.-F. Wang, S.-J. Liu, and C.-H. Lin (2009), "Improved algorithms for the gene team problem," in Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2009), Lecture Notes in Computer Science, vol. 5573, pp. 61-72. (EI, SCI)
[C6]
C.-C. Yu, W.-K. Hon, and B.-F. Wang (2009), "Efficient data structures for the orthogonal range successor problem," in Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009), Lecture Notes in Computer Science, vol. 5609, pp. 96-105. (EI, SCI)
[C7]
L.-P. Yeh and B.-F. Wang (2008), "Efficient algorithms for the k smallest cuts enumeration," in Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Lecture Notes in Computer Science, vol. 5092, pp. 434-443. (EI, SCI)
[C8]
C.-Y. Chan, H.-I Yu, W.-K. Hon, and B.-F. Wang (2007), "A faster query algorithm for the text fingerprinting problem," in Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Lecture Notes in Computer Science, vol. 4698, pp. 123-135. (EI, SCI)
[C9]
T.-C. Lin, H.-I Yu, and B.-F. Wang (2006), "Improved algorithms for the minmax regret 1-center problem," in Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, vol. 4288, pp. 537-546. (EI, SCI)
[C10]
H.-I Yu, T.-C. Lin, and B.-F. Wang (2006), "Improved algorithms for the minmax regret 1-median problem," in Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON 2006), Lecture Notes in Computer Science, vol. 4112, pp. 52-62. (EI, SCI)
[C11]
B.-F. Wang, Y.-H. Hsieh, and L.-P. Yeh (2003), "Efficient algorithms for the ring loading problem with demand splitting," in Proceedings of the 2003 Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, vol. 2832, pp. 517-526. (EI, SCI)
[C12]
H.-Y. Yu and B.-F. Wang (2002), "An improved algorithm for finding k-centrums on weighted trees," in Proceedings of the 2002 International Conference on Parallel and Distributed Systems, received the best paper award.
[C13]
B.-F. Wang, S.-C. Ku, and Y.-H. Hsieh (2002) "The conditional location of a median path," in Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON 2002), Lecture Notes in Computer Science, vol. 2387, pp. 494-503, 2002. (EI, SCI)
[C14]
S.-C. Ku, C.-J. Lu, B.-F. Wang, and P.-C. Lin (2001), "Efficient algorithms for two generalized 2-median problems on trees," in Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC2001), Lecture Notes in Computer Science, vol. 2223, pp. 768-778, 2001.
[C15]
S.-C. Ku, T.-K. Hung, B.-F. Wang, and J.-J. Lin (2001), "Constructing edge-disjoint spanning trees on product networks," in Proceedings of the 2001 International Conference on Parallel and Distributed Processing Techniques and Applications.
[C16]
B.-F. Wang and J.-J. Lin (2000), "Finding a two-core of a tree in linear time," in Proceedings of the 11th Annual International Symposium on Algorithms and Computation (ISAAC2000), Lecture Notes in Computer Science, vol. 1969, Springer, pp. 467-478. (EI, SCI)
[C17]
B.-F. Wang, S.-C. Ku, K.-H Shi, T.-K. Hung, and P.-S. Liu (1999), "Parallel algorithms for the tree bisector problem and applications," in Proceedings of the 1999 International Conference on Parallel Processing, pp. 192-199. (NSC-88-2213-E-007-039)
[C18]
H.-Y. Kao, Y.-C. Kuo, S.-T. Huang, and B.-F. Wang (1998), "Design and implementation of a PC-based video-on-demand system," in Proceedings of the 12th International Conference on Information Networking (ICOIN-12), pp. 42-45, Tokyo, Japan. (NSC-85-2221-E-007-018)
[C19]
S.-C. Ku and B.-F. Wang (1998), "Optimally locating a structured facility of a specified length in a weighted tree network," in Proceedings of the 1998 International Parallel Processing Symposium, pp. 370-374. (NSC-87-2213-E-007-066)
[C20]
B.-F. Wang and S. Olariu (1997), "On the power of the mesh with hybrid buses," in Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks, pp. 172-178.
[C21]
S.-C. Ku, W.-K. Shih, and B.-F. Wang (1997), "Efficient parallel algorithms for optimally locating a k-leaf tree in a tree network," in Proceedings of the 1997 International Conference on Parallel Processing, pp. 16-19. (NSC-84-2221-E-007-002)
[C22]
C.-H. Peng, B.-F. Wang, and J.-S. Wang (1995), "Recognizing depth-first-search trees in parallel," in Proceedings of the 1995 International Parallel Processing Symposium, Santa Barbara, California, pp. 101-105.
[C23]
D.-J. Shyu, B.-F. Wang, and C.-Y. Tang (1995), "The emulation problem on trees," in Proceedings of the 1995 International Parallel Processing Symposium, Santa Barbara, California, pp. 251-255. (NSC-84-0408-E-007-006)
[C24]
D.-J. Shyu, B.-F. Wang, and C.-Y. Tang (1994), "An Efficient emulation for tree-connected networks," in Proceedings of the 1994 International Conference on Parallel and Distributed Systems, Hsinchu, Taiwan, pp. 502-507. (NSC-84-0408-E-0007-006)
[C25]
D.-J. Shyu, B.-F. Wang, and C.-Y. Tang (1994), "Fast algorithms for simulating the CRCW shared-memory computer on reconfigurable meshes," in Proceedings of the 1994 International Conference on Parallel Processing, vol. III, Chicago, Illinois, U.S.A., pp. 143-146. (NSC-83-0408-E-007-013)
[C26]
B.-F. Wang, G.-H. Chen, and H. Li (1991), "Fast algorithms for some arithmetic and logic operations," in Proceedings of the 1991 National Computer Symposium, vol. 1, Chung-Li, Taiwan, pp. 178-183.
[C27]
B.-F. Wang, G.-H. Chen, and M.-S. Yu (1991), "Cost-optimal parallel algorithms for constructing B-trees," in Proceedings of the 1991 International Conference on Parallel Processing, vol. III, Chicago, Illinois, U.S.A., pp. 294-295.
[C28]
B.-F. Wang, G.-H. Chen, and C.-C. Hsu (1991), "Bitonic sort with an arbitrary number of keys," in Proceedings of the 1991 International Conference on Parallel Processing, vol. III, Chicago, Illinois, U.S.A., pp. 58-61.
[C29]
B.-F. Wang, G.-H. Chen, and H. Li (1991), "Configurational computation: a new computation method on processor arrays with reconfigurable bus systems," in Proceedings of the 1991 International Conference on Parallel Processing, vol. III, Chicago, Illinois, U.S.A., pp. 42-49.
[C30]
B.-F. Wang, G.-H. Chen, and H. Li (1990), "Configurational computation on processor arrays with reconfigurable bus systems," in Proceedings of the First Workshop on Parallel Processing, Hsinchu, Taiwan, pp. 96-105.
[C31]
B.-F. Wang and G.-H. Chen (1990), "Constant time algorithms for sorting and computing convex hulls," in Proceedings of the 1990 International Computer Symposium, vol. 2, Hsinchu, Taiwan, pp. 607-612.
[C32]
B.-F. Wang and G.-H. Chen (1990), "An O(1) time algorithm for generating computation tree forms," in Proceedings of the 1990 International Computer Symposium, vol. 2, Hsinchu, Taiwan, pp. 465-470.
[C33]
B.-F. Wang, C.-J. Lu, and G.-H. Chen (1990), "Constant time algorithms for the transitive closure problem and its applications," in Proceedings of the 1990 International Conference on Parallel Processing, vol. III, Chicago, Illinois, U.S.A., pp. 52-59.