Theory@CSBB LAB - Analysis and design of algorithms

''The main interest of Theory Group of CSBB LAB is the field of Analysis and design of algorithms.''\n\nCurrently, most of group members are working in the field algorithmic graph theory, and some others work on computational biology. Basically, we focuses upon practical and theoretical applications for Algorithms.

\n! Journals\nThis list is sorted by the Impact Factor of [[JCR|http://portal.isiknowledge.com/portal.cgi?DestApp=JCR&Func=Frame]].\n* [[ACM Computing Surveys|http://portal.acm.org/browse_dl.cfm?linked=1&part=journal&idx=J204&coll=portal&dl=ACM&CFID=10774764&CFTOKEN=37717198]] -- IF 10.037\n* [[SIAM Review|http://epubs.siam.org/SIREV/]] -- IF 6.118\n* [[Bioinformatics|http://bioinformatics.oxfordjournals.org/]] -- IF 5.742\n* [[Journal of Computational Biology|http://www.worldscinet.com/jbcb/jbcb.shtml]] -- IF 3.241\n* [[Journal of the ACM|http://portal.acm.org/browse_dl.cfm?linked=1&part=journal&idx=J401&coll=ACM&dl=ACM]] -- IF 2.414\n* [[Computational Complexity|http://www.springerlink.com/content/1420-8954/]] -- IF 2.000\n* [[Foundations of Computational Mathematics|http://www.springerlink.com/link.asp?id=106038]] -- IF 1.500\n* [[SIAM Journal on Computing|http://epubs.siam.org/SICOMP/]] -- IF 1.306\n* [[Journal of Complexity|http://www.sciencedirect.com/science/journal/0885064X]] -- IF 1.186\n* [[Information and Computation|http://www.sciencedirect.com/science/journal/08905401]] -- IF 1.053\n* [[Journal of Computer and System Sciences|http://www.sciencedirect.com/science/journal/00220000]] -- IF 1.030\n* [[Algorithmica|http://www.springerlink.com/openurl.asp?genre=journal&eissn=1432-0541]] --- IF 0.923\n* [[Acta Informatica|http://www.springerlink.com/openurl.asp?genre=journal&issn=0001-5903]] -- IF 0.922\n* [[Computational Optimization and Applications| http://www.springerlink.com/openurl.asp?genre=journal&issn=0926-6003]] -- IF 0.815\n* [[Theoretical Computer Science|http://www.sciencedirect.com/science/journal/03043975]] -- IF 0.743\n* [[SIAM Journal on Discrete Mathematics|http://epubs.siam.org/SIDMA/sidma_toc.html]] -- IF 0.636\n* Journal of Combinatorial Theory, Series [[A|http://www.sciencedirect.com/science/journal/00973165]] (IF 0.485) and [[B|http://www.sciencedirect.com/science/journal/00958956]] (IF 0.618)\n* [[Discrete Applied Mathematics|http://www.sciencedirect.com/science/journal/0166218X]] -- IF 0.585\n* [[Networks|http://www3.interscience.wiley.com/cgi-bin/jhome/32046]] -- IF 0.571\n* [[Computers and Operations Research|http://www.sciencedirect.com/science/journal/03050548]] -- IF 0.562\n* [[Journal of Combinatorial Optimization|http://www.springerlink.com/openurl.asp?genre=journal&issn=1382-6905]] -- IF 0.560\n* [[Information Sciences|http://www.sciencedirect.com/science/journal/00200255]] -- IF 0.540\n* [[Theory of Computing Systems|http://www.springerlink.com/openurl.asp?genre=journal&issn=1432-4350]] -- IF 0.538\n* [[Combinatorics, Probability and Computing|http://journals.cambridge.org/action/displayJournal?jid=CPC]] -- IF 0.489\n* [[Journal of Graph Theory|http://www3.interscience.wiley.com/cgi-bin/jhome/35334?CRETRY=1&SRETRY=0]] -- IF 0.460\n* [[Information Processing Letters|http://www.sciencedirect.com/science/journal/00200190]] -- IF 0.453\n* [[Combinatorica|http://www.springerlink.com/openurl.asp?genre=journal&eissn=1439-6912]] -- IF 0.388\n* [[Discrete Mathematics|http://www.sciencedirect.com/science/journal/0012365X]] -- IF 0.374\n* [[European Journal of Combinatorics|http://www.sciencedirect.com/science/journal/01956698]] -- IF 0.303\n* [[Graphs and Combinatorics| http://www.springerlink.com/openurl.asp?genre=journal&issn=0911-0119]] -- IF 0.235\n\n''Some good journals not yet in JCR''\n* [[ACM Transactions on Algorithms|http://portal.acm.org/browse_dl.cfm?linked=1&part=transaction&idx=J982&coll=portal&dl=ACM&CFID=71912801&CFTOKEN=62408165]] -- \n* [[Journal of Discrete Algorithms|http://www.sciencedirect.com/science/journal/15708667]] --\n* [[Journal of Graph Algorithms and Applications|http://www.cs.brown.edu/publications/jgaa/]] ---\n* [[Theory of Computing|http://theoryofcomputing.org]] --\n* [[Random Structures and Algorithms|http://www3.interscience.wiley.com/cgi-bin/jhome/38107]] \n\n! Conference Rankings\nThe original data is from Guofei Gu's [[Computer Science Conference Rankings|http://www-static.cc.gatech.edu/~guofei/CS_ConfRank.htm]]. The following is some conferences which are close to our group.\n\nAREA: Algorithms and Theory\n* Rank 1:\n** STOC: ACM Symp on Theory of Computing\n** FOCS: IEEE Symp on Foundations of Computer Science\n** SODA: ACM/SIAM Symp on Discrete Algorithms\n* Rank 2:\n** STACS: Symp on Theoretical Aspects of Computer Science\n** CC: IEEE Symp on Computational Complexity\n** WADS: Workshop on Algorithms and Data Structures\n** MFCS: Mathematical Foundations of Computer Science\n** SWAT: Scandinavian Workshop on Algorithm Theory\n** ESA: European Symp on Algorithms\n** IPCO: MPS Conf on integer programming & comb optimization\n** ISTCS: Israel Symp on Theory of Computing and Systems\n** ISAAC: Intl Symp on Algorithms and Computation\n** LATIN: Intl Symp on Latin American Theoretical Informatics\n** RECOMB: Annual Intl Conf on Comp Molecular Biology\n* Rank 3:\n** ASIAN: Asian Computing Science Conf\n** FCT: Fundamentals of Computation Theory\n** WG: Workshop on Graph Theory\n** CIAC: Italian Conf on Algorithms and Complexity\n** ICCI: Advances in Computing and Information\n** AWTI: Argentine Workshop on Theoretical Informatics\n** CATS: The Australian Theory Symp\n** COCOON: Annual Intl Computing and Combinatorics Conf\n** CITB: Complexity & info-theoretic approaches to biology\n** DMTCS: Intl Conf on Disc Math and TCS\n\n!Others\n** [[SIAM News|http://www.siam.org/news/]]\n** [[Bulletin of EATCS|http://www.liacs.nl/~beatcs]] -- [[Computational Complexity Column|http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/]]\n**[[ACM SIGACT News|http://portal.acm.org/browse_dl.cfm?linked=1&part=newsletter&idx=J697]]\n**[[Optima|http://www.ise.ufl.edu/~optima/]] --- newsletter of the Mathematical Programming Society\n**[[TheoryMatters|http://theorymatters.org/pmwiki/pmwiki.php]]\n**[[ComplexityZoo|http://qwiki.caltech.edu/wiki/Complexity_Zoo]]\n**[[Algorithmist|http://www.algorithmist.com/index.php/Main_Page]]\n**[[Parawiki|http://www.parawiki.org/index.php/Main_Page]]\n**[[Compendium of NPO|http://www.nada.kth.se/~viggo/wwwcompendium/]]\n**[[Design and Analysis of Computer Algorithms|http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html]]\n**[[Compendium of Parameterized Problems|http://bravo.ce.uniroma2.it/home/cesati/research/compendium/]]\n**[[Graph Coloring Page|http://web.cs.ualberta.ca/~joe/Coloring/index.html]]\n**[[The P-versus-NP page|http://www.win.tue.nl/~gwoegi/P-versus-NP.htm]]\n**[[The Stony Brook Algorithm Repository|http://www.cs.sunysb.edu/~algorith/index.html]]\n**[[Graphs :: Theory - Algorithms - Complexity|http://people.freenet.de/Emden-Weinert/graphs.html]]\n**[[Information System on Graph Class Inclusions v2.0|http://wwwteo.informatik.uni-rostock.de/isgci/]]\n**[[RIOT -- Remote Interactive Optimization Testbed|http://riot.ieor.berkeley.edu/riot/index.html]]\n**[[Average-Case Complexity Forum|http://www.uncg.edu/mat/avg.html]]\n**[[Information-Based Complexity|http://www.ibc-research.org/]]\n**[[Springer Online Reference Works -- Encyclopaedia of Mathematics|http://eom.springer.de/]], Edited by Michiel Hazewinkel

[[About]]\n[[Home]]\n[[Academic]]

! WSPAA'06 \n[[Algorithm & Biocompuing Lab of NCNU CSIE|http://alg.csie.ncnu.edu.tw/]] and we cooperated to host the Workshop on String Processing and Approximation Algorithms National Tsing Hua University, Hsinchu, 17&24 June 2006\n\nThe Webpage: [[WSPAA|http://algorithm.cs.nthu.edu.tw/WSPAA06/]]

<html><img src="Al-Khwarizmi_2.jpeg" alt="al-Khwarizmi" style="float:left;margin: 5pt" width="200" />\n\nThe word algorithm comes from the name of the 9th century Persian mathematician Abu Abdullah Muhammad bin Musa al-Khwarizmi. The word algorism originally referred only to the rules of performing arithmetic on numbers. And the meaning of the word algorithm comes from early, too. A famous example is Euclid's Algorithm, which computes the greatest common divisor (GCD) of two integers.\n\n<img src="JohnvonNeumann-LosAlamos.png" alt="John von Neumann" style="float:right ;margin: 5pt" width="200" />\n\nWe often take <a href="http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Von_Neumann.html">John von Neumann</a> as the father of computer science. John von Neumann is a great mathematician; He made important contributions in quantum physics, functional analysis, set theory, economics and many other mathematical fields. He also built a computer and dedicated to preach the importance of computer. Moreover, <a href="http://www.ieee.org/">IEEE</a> awards annually for outstanding achievements in computer-related science and technology by the <a href="http://en.wikipedia.org/wiki/IEEE_John_von_Neumann_Medal">John von Neumann Medal</a>.\n\nThe famous stories of John von Neumann might be about the ability of computing in mind and good memory. But he is not the only one with that abilities in history. Euler can do it, too. <a href="http://en.wikipedia.org/wiki/Euler">Leonhard Euler</a> is one of greatest mathematicians, and might be the greatest algorithmist. \n\n"Read Euler, read Euler, he is the master of us all." by P.S.de Laplace\n\n<img src="Euler_8.jpeg" alt="Euler" style="float:left;margin: 5pt" width="200"/>\n\nEuler worked in almost all areas of mathematics: geometry, calculus, trigonometry, algebra, and number theory, not to mention continuum physics, lunar theory and other areas of physics. In addition, he also gives some results considered to be the first theorem of graph theory and planar graph theory, i.e., Eulerian circuit of Seven Bridges of Königsberg.\n\nNowadays, theoretical computer science becomes more and more important. Theoretical computer science forms a new field out of mathematics, and still absorbs the nutrition from mathematics and real world. There are a lots of complicated researches which rely heavily on the computing power. Algorithms have not only the mathematical interests, but also have huge impact to the real world, any slight improvement of algorithms might be helpful to reduce a huge waste of time and other resources.\n</html>\n<<<\n"The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. (From [[ACM SIGACT|http://sigact.acm.org/]])"\n<<<\n\n''Some articles discussed the works and perspectives about Algorithms.''\n* [[Beyond the algorithmization of the sciences|http://doi.acm.org/10.1145/1125944.1125967]], by Thomas A. Easton. "Algorithmic thinking is transforming both the descriptive sciences and the humanities, bringing them all closer to the mathematical core of computer science."\n* [[The Algorithm: Idiom of Modern Science|http://www.cs.princeton.edu/~chazelle/pubs/algorithm.html]] by Bernard Chazelle\n* [[Computational Complexity|http://www.esi2.us.es/~mbilbao/complexi.htm]], by Leslie Hall, The Johns Hopkins University\n* [[Computational Thinking|http://www.cs.cmu.edu/afs/cs/usr/wing/www/publications/Wing06.pdf]], CACM vol. 49, no. 3, March 2006, pp. 33-35. [[Chinese translation|http://chn.blogbeta.com/127.html]]. Talk ([[pdf|http://www.cs.cmu.edu/afs/cs/usr/wing/www/ct06.pdf]],[[ppt|http://www.cs.cmu.edu/afs/cs/usr/wing/www/ct06.ppt]]).\n* [[Theoretical Computer Science Cheat Sheet|http://portal.acm.org/citation.cfm?id=242581.242585]], ACM SIGACT News, Steve Seiden.\n* [[Algorithm characterizations|http://en.wikipedia.org/wiki/Algorithm_characterizations]] From Wikipedia, the free encyclopedia

[[Back to LAB|index.html]]\n\n''Group''\n[[Home]]\n[[About]]\n[[Meetings]]\n[[Events]]\n[[Academic]]\n[[Publications]]\n\n''Members''\n[[劉至善]]\n[[崔愷文]]\n\n\n''Links''\n**[[ACM SIGACT|http://sigact.acm.org/]]\n**[[ECCC|http://eccc.uni-trier.de/eccc/]]\n**[[EATCS|http://www.eatcs.org/]]\n**[[DIMACS|http://dimacs.rutgers.edu/]]\n**[[BCC|http://www.maths.qmul.ac.uk/~pjc/bcc/]]\n\n\n[[TheoryCalendar|http://www.cs.uiowa.edu/theoryc/]]\n[[comp-sci-theory|http://groups.yahoo.com/group/comp-sci-theory/]]\n[[theory-edge|http://groups.yahoo.com/group/theory-edge/]]\n\n''[[RSSFeed| theory.xml]]''\n\n[img[mark|school_mark.png]]

\n!Graph Algorithms Meeting, 2007 Fall\n''This meeting focus on Algorithmic Graph Theory.''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Chih Shan Liu|mailto:d9562833@oz.nthu.edu.tw]]\nTime : 17:30~19:00, Friday, Biweekly\nRoom : Room 533, CSEE building.\n[[Schedule of talks for 2007 Fall]]\n\n\n!Special Topics in Algorithms (II), 2007 Spring\n''This seminar is about approximation algorithms.''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Yun-Sheng Chung|mailto:d938336@oz.nthu.edu.tw]]\nTime : PM 1:10--3:00, Thursday\nRoom : Meeting Room 421, 4F, General Building II\nReadings : Approximation Algorithms, by Vijay V. Vazirani\n\n!Graph Algorithms Meeting, 2007 Spring\n''This meeting focus on Algorithmic Graph Theory.''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Chih Shan Liu|mailto:d9562833@oz.nthu.edu.tw]]\nTime : 16:30~18:00, Friday, Biweekly\nRoom : Room 533, CSEE building.\n[[Schedule of talks for 2007 Spring|GAM2007Spring.html]]\n\n!Graph Algorithms Meeting, 2006 Fall\n''This meeting focus on Algorithmic Graph Theory. (domination problems on special graphs)''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Chih Yi Huang|mailto:BarrosH@gmail.com]]\nTime : PM 5:30 -- 7:00, Friday, Biweekly\nRoom : Prof. Tang's office room.\n[[Schedule of talks for 2006 Fall|GAM2006Fall.html]]\n\n!Special Topics in Algorithms (I), 2006 Fall\n''This seminar is about Probabilistic Methods.''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Yun-Sheng Chung|mailto:d938336@oz.nthu.edu.tw]]\nTime : 3:20--5:10 PM, Thursday\nRoom : Room 128, CSEE building.\nReadings : The Probabilistic Method, 2nd Ed, by Noga Alon and Joel Spencer, 2000. \nSome resources and materials are placed on ''/home/calab/upload'' of this server. [[The slides of Prof. Shi-Chun Tsai|http://www.csie.nctu.edu.tw/~sctsai/prob/]] and [[Prof. Spencer's lecture note of asymptotics|http://cs.nyu.edu/cs/faculty/spencer/rg06/asympnotes.pdf]]\n\n!Special Topics in Algorithms (II), 2006 Spring\n''This seminar is about approximation algorithms.''\n\nInstructor: [[Prof. Tang|http://www.cs.nthu.edu.tw/~cytang/]]\nOrganizer : [[Yun-Sheng Chung|mailto:d938336@oz.nthu.edu.tw]]\nTime : PM 1:10--3:00, Thursday\nRoom : Classroom 6, CSME building.\nReadings : Ausiello et al., Complexity and Approximation -- Combinatorial Optimization Problems and Their Approximability Properties

# Y.H. Chen, G.-L. Liao and C.Y. Tang (2007), Approximation Algorithms for 2-source Minimum Routing Cost k-tree Problems, 2007 International Conference on Computational Science and Its Applications (ICCSA2007), LNCS, Springer Verlag.\n# Y.H. Chen and C.Y. Tang (2006), The Bottleneck Tree Alignment Problems, 2006 International Conference on Computational Science and Its Applications (ICCSA2006), LNCS, Springer Verlag, 3982, pp. 631-637.\n# F. Kuo, Y.-C. Lee, C.Y. Tang (2004), The Development of RFID in Healthcare in Taiwan, 4th International Conference on Electronic Business (ICEB2004), pp. 340-345.\n# Y.H. Chen, B.Y. Wu and C.Y. Tang (2004), Approximation Algorithms for k-source Bottleneck Routing Cost Spanning Tree Problems (extended abstract), 2004 International Conference on Ccomputational Science and Its Applications (ICCSA2004), LNCS, pp. 355-366.\n# C.L. Lu, Z.Y. Su and C.Y. Tang (2001), A New Measures of Edit Distance Between Labeled Trees, 7th Annual International Computing and Combinatorics Conference (COCOON2001), LNCS, Springer Verlag, 2108, pp.338-348. \n\n# C.M. Lin, Y.T. Tsai and C.Y. Tang (2006), Balancing Minimum Spanning Trees and Multiple-Source Minimum Routing Cost Spanning Trees on Metric Graphs, Information Processing Letters, 99, pp. 64-67. (EI, SCI)\n# P.-H. Huang, Y.-T. Tsai and C.Y. Tang (2006), A Near-Quadratic Algorithm for the Alpha-Connected Two-Center Problem, Journal of Information Science and Engineering, 22, pp. 1317-1324. (SCIE)\n# C.-M. Lee, L.-J. Hung, M.-S. Chang and C.Y. Tang (2005), An Improved Algorithm for the Maximum Agreement Subtree Problem, Information Processing Letters, 94, pp. 211-216. (EI, SCI)\n# Y.H. Chen, B.Y. Wu and C.Y. Tang (2005), Approximation Algorithms for Some k-source Shortest Paths Spanning Tree Problems, Networks, 47, pp. 147-156. (EI, SCI)\n# C.L. Lu, S.L. Peng and C.Y. Tang (2003), Efficient Minus and Signed Domination in Graphs, Theoretical Computer Science, 301, pp. 381-397.\n# B.Y. Wu, K.-M. Chao and C.Y. Tang (2002), Light Graphs with Small Routing Cost, Networks, 39, pp. 130-138. (EI, SCI)\n# C.L. Lu, M.-T. Ko and C.Y. Tang (2002), Perfect Edge Domination and Efficient Edge Domination in Graphs, Discrete Applied Mathematics, 119, pp. 229-252. (EI, SCI)\n# C.L. Lu and C.Y. Tang (2002), Weighted Efficient Domination Problem on Some Perfect Graphs, Discrete Applied Mathematics, 117, pp. 163-182. (EI, SCI)\n# B.-K. Lu, F.-R. Hsu and C.Y. Tang (2001), Finding the Shortest Boundary Guard of A Simple Polygon, Theoretical Computer Science, 263, pp. 113-121. (EI, SCI) \n\n[[More|http://www.cs.nthu.edu.tw/~cytang/more_papers.htm#j_alg]]

Analysis and design of algorithms

Theory@CSBB LAB

[img[photo| ]]\n* Name : Chih-Shan Liu\n* Office : Room 315, CSME building.\n* Phone : \n* E-mail : \n* Fields of interest : Graph Theory

[img[photo| ]]\n* Name : Lu, Shao-chia\n* Office : Room 315, CSME building.\n* Phone : \n* E-mail : g9562643@oz.nthu.edu.tw\n* Fields of interest :

[img[photo| ]]\n* Name : \n* Office : Room 315, CSME building.\n* Phone : +886 3 5715131-33918\n* E-mail : \n* Fields of interest :

[img[photo| ]]\n* Name : Yen-Lin Huang\n* Office : \n* Phone : \n* E-mail : \n* Fields of interest :

[img[AbnerCYH|http://photos22.flickr.com/32709870_648939ebfa_o.jpg]]\n* Name : Abner Chih Yi Huang (A.C.Y. Huang)\n* Office : Room 315, CSME building.\n* Phone : +886 3 5715131-33918\n* E-mail : abnercyh@gmail.com\n* Fields of interest : Combinatorics, Complexity, Algorithmics\n* ''[[Personal Homepage|http://barrosh.myweb.hinet.net]]''