*Mahjoub, A. & Mailfert, J. ,[[On the independent dominating set polytope|GAM2006Fall/20060915Huang.ref.1.pdf]], European Journal of Combinatorics, 2006, 27, 601-616\n*M. Bouchakour and A.R. Mahjoub, [[One-node cutsets and the dominating set polytope|GAM2006Fall/20060915Huang.ref.2.pdf]], Discrete Math. 165–166 (1997), pp. 101–123.\n*Ehrenborg, R. & Hetyei, G. [[The topology of the independence complex|GAM2006Fall/20060915Huang.ref.3.pdf]], European Journal of Combinatorics, 2006, 27, 906-923.\n*Damian-Iordache, M. & Pemmaraju, S.V., [[Hardness of Approximating Independent Domination in Circle Graphs|GAM2006Fall/20060915Huang.ref.4.pdf]], ISAAC '99\n*Bogdanov, A., Obata, K., Trevisan, L. A linear lower bound on the query complexity of property testing algorithms for 3-coloring in bounded-degree graphs, Proc. 43rd FOCS (2002), 93-102.\n*Bogdanov, A., Trevisan, L. Lower bounds for testing bipartiteness in dense graphs, ECCC 64 (2002).\n*Fischer, E. Testing graphs for colorability properties, Proc. 12th SODA (2001), 873-882.\n*Goldreich, O., Ron, D. On estimating the average degree of a graph, ECCC 11, 13 (2004).\n*Alon, N. Testing subgraphs in large graphs, Random Structures and Algorithms 21 (2002), 359-370.\n*Alon, N., Krivelevich, M. Testing k-colorability, SIAM J. Discrete Math. 15 (2002), 211-227.\n*Alon, N., Shapira, A. Testing subgraphs in directed graphs, Proc. 35th STOC (2003), 700-709.\n*Alon, N., Shapira, A. A characterization of easily testable induced subgraphs, Proc. 15th SODA (2004), 935-944.\n*Bender, M., Ron, D. Testing properties of directed graphs: acyclicity and connectivity, Random Structures and Algorithms 20 (202), 184-205.\n*Goldreich, O., Ron, D. A sublinear bipartite tester for bounded degree graphs, Combinatorica 19 (1999), 335-373.\n*Kaufman, T., Krivelevich, M., Ron, D. Tight bounds for testing bipartiteness in general graphs, Proc. RANDOM-APPROX (2003), 341-353.\n*Parnas, M., Ron, D. Testing the diameter of graphs, Random Structures and Algorithms 20 (2002), 165-183.\n*Kumar, R., Rubinfeld, R., Sublinear time algorithms, Samir Khuller's Algorithms column in SIGACT News 2003.\n*Chazelle, B., Rubinfeld, R., Trevisan, L. Approximating the minimum spanning tree weight in sublinear time, Proc. 28th ICALP (2001), 190-200.\n*Czumaj, A., Sohler, C. Estimating the weight of metric minimum spanning trees in sublinear-time Proc. 36th STOC (2004).\n*Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C. Sublinear-time approximation of Euclidean minimum spanning tree, Proc. 14th SODA (2003), 813-822.
* Chung-Shou Liao and D. T. Lee, [[Power domination problem in graphs|GAM2006Fall/20060915Liu.ref.1.pdf]],the Eleventh International Computing and Combinatorics Conference 2005\n* Yu-Yen Chien, [[Power Domination on Graphs|GAM2006Fall/20060915Liu.ref.2.pdf]], Master Thesis, NTU. [[Another|GAM2006Fall/20060915Liu.ref.3.pdf]]\n* Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith, [[Parameterized Power Domination Complexity|GAM2006Fall/20060915Liu.ref.4.pdf]], Technical Report,Department of Computer Science of RWTH Aachen University\n* Sandi Klavˇzar, P. Dorbec, M. Mollard and S. Špacapan, [[Power domination in product graphs|GAM2006Fall/20060915Liu.ref.5.pdf]], manuscript.\n* Jiong Guo, Rolf Niedermeier, Daniel Raible, [[Improved Algorithms and Complexity Results for Power Domination in Graphs|GAM2006Fall/20060915Liu.ref.6.pdf]]. pp. 172-184, Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings. Lecture Notes in Computer Science 3623 Springer 2005\n* Min Zhao, Liying Kang, Gerard J. Chang, [[Power domination in graphs|GAM2006Fall/20060915Liu.ref.7.pdf]]\n
''This meeting focus on Algorithmic Graph Theory, but we emphasized the domination problems on special graph, such as power domination and independent domination.''\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|http://www.cs.nthu.edu.tw/~cytang/]]'s office room.
''For speaker'':\nPlease send the information of your talk to [[oganizer|mailto://BarrosH@gmail.com]] before the meeting few days. The format is\n> Speaker: \n> Topic: \n> Paper: \n> Abstract:\n> Reference:\nFor example:\n> Speaker: 黃智沂\n> Topic: Greedy algorithms\n> Paper: Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chapter 16, Introduction to Algorithms. 2nd ed. \n> Abstract: an algorithm that follows the problem solving metaheuristic of making the locally optimum choice at each stage with the hope of finding the global optimum.\n> Reference: T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588\n
! 2006-09-16\nWe changed weekly to biweekly.
TalkSchedule
To get started with this blank TiddlyWiki, you'll need to modify the following tiddlers:\n* SiteTitle & SiteSubtitle: The title and subtitle of the site, as shown above (after saving, they will also appear in the browser title bar)\n* MainMenu: The menu (usually on the left)\n* DefaultTiddlers: Contains the names of the tiddlers that you want to appear when the TiddlyWiki is opened\nYou'll also need to enter your username for signing your edits: <<option txtUserName>>
[[Back to LAB|index.html]]\n[[Back to TheoryGroup|theory.html]]\n\nBulletinBoard\nTalkSchedule\nBibFormat\nAboutUs\n\n''Members''\n劉至善\n崔愷文\n葉庭熙\n黃智沂\n謝明鋒\n李維陞\n呂紹甲\n\n[img[mark|school_mark.png]]
Graph Algorithms Meeting, 2006 Fall
Schedule of Talks
[img[GraphClasses|http://static.flickr.com/82/244564415_e04f1fe517.jpg]]\nPress [[Here|http://www.flickr.com/photos/barrosh/244564415/]] to obtain the larger pic.\n\n*2006-09-15\n** Speaker: 劉至善\n** Topic: [[Power domination on probe interval graphs|GAM2006Fall/20060915Liu.ppt]]\n** Paper: None\n** Abstract: Breif Introduction to power domination and probe interval graph.\n** [[20060915.Ref.Liu]]\n** Speaker: 黃智沂\n** Topic: [[Independent Domination Set on Chordal Graphs: complexity and approximation|GAM2006Fall/20060915Huang.pdf]]\n** Paper: None\n** Abstract: Breif Introduction to independent domination and chordal graph.\n** [[20060915.Ref.Huang]]\n\n\n* 2006-09-29\n** Speaker: 李維陞\n** Topic: [[Polynomial time algorithm on some restricted graph|GAM2006Fall/20060929Lee.ppt]]\n** Paper: [[Treewidth, partial k-trees, and chordal graphs|http://www.ii.uib.no/~pinar/chordal.pdf]], Pinar Heggernes, Partial curriculum in Advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway, 2005.\n** Abstract: Many graph problem that are NP Hard on general graph, have polynomial time solutions if the input graph has bounded treewidth or if it belongs to a restricted graph class. Therefore, we discuss these good property on graphs that can help us to solve graph problems in polynomial time.\n** Reference:\n***Douglas B. West, introduction to graph theory, chap 5\n***Juraj Bosak, Decompositions of Graphs, chap 1~3\n** Speaker: 呂紹甲\n** Topic: [[Roman Domination on Strongly Chordal Graph|GAM2006Fall/20060929Lu.pdf]]\n\n* 2006-10-13\n** Speaker: 崔愷文\n** Topic: [[Finding A Minimum Independent Dominating Set In A Permutation Graph|GAM2006Fall/20061013Tsuei.ppt]]\n** Paper: Finding A Minimum Independent Dominating Set In A Permutation Graph, Mikhail J. ATALLAH , Glenn K. MANACHER , J. URRUTIA, Discrete Applied Mathematics 21 (1988) 177-183\n\n* 2006-10-27\n** Speaker: Cheng Hsun Kao\n** Topic: [[ALGORITHMIC ASPECT OF k-TUPLE DOMINATION IN GRAPHS|GAM2006Fall/20061027Kao.ppt]]\n** Paper: ALGORITHMIC ASPECT OF k-TUPLE DOMINATION IN GRAPHS, Chung Shou Liao and Gerard J. Chang, TAIWANESE JOURNAL OF MATHEMATICS Vol. 6, No. 3, pp. 415-420,September 2002\n\n* 2006-11-10\n** Speaker: 劉至善\n** Topic: [[Power domination in block graphs|GAM2006Fall/20061110Liu.ppt]]\n** Paper: [[Power domination in block graphs|GAM2006Fall/20061110Liu.ref.3.pdf]], TCS 2006.\n** Abstract: \n** Reference: \n*** [[A note on power domination in grid graphs|GAM2006Fall/20061110Liu.ref.2.pdf]], Michael Dorfling, Michael A. Henning, Discrete applied mathematics 154(2006).\n*** [[Placing monitoring devices in electric power networks modelled by block graphs|GAM2006Fall/20061110Liu.ref.1.pdf]], Ars Combinatoria Volume 79, 2006\n\n* 2006-11-24\n** Speaker: 黃智沂\n** Topic: [[Graphs Connectivity|GAM2006Fall/20061124Huang.pdf]]\n** Paper: [[Testing Connectivity of Graphs|http://etds.lib.ntu.edu.tw/etdservice/view_metadata?etdun=U0001-1906200616134600]], Hsuan Chang Chen, Master thesis, Graduate Institute of Computer Science and Information Engineering , NTU, 2006.\n** Abstract: Graph connectivity is an important topic in network construction.For example, when we maintain a network which has existed for a longtime, we always want to know if the nodes of the network are still able to communicate with each other. However, a network can be a huge structure, and we don't like to check the whole network to know the answer. So we use an approximation algorithm technique called ``property testing' and only check a small set of nodes of the network to know whether the network is still good to use for communication. \n** Reference:\n*** [[Property testing in bounded degree graphs|GAM2006Fall/20061027Huang.ref.1.pdf]], O. Goldreich and D. Ron. Algorithmica, Vol. 32 (2), pages 302-343, 2002.\n\n* 2006-12-15\n** Speaker: 呂紹甲\n** Topic: From a simple elimination ordering to a strong elimination ordering in linear time\n** Paper: [[From a simple elimination ordering to a strong elimination ordering in linear time|GAM2006Fall/20061215Lu.ref.pdf]], Information Processing Letters 86 (2003) 299–302\n** Abstract: \n** Reference:\n***\n\n* 2006-12-22\n** Speaker: 謝明鋒\n** Topic:\n** Paper: None\n** Abstract: \n** Reference:\n***\n\n* 2007-01-05\n** Speaker: 李維陞\n** Topic:\n** Paper: None\n** Abstract: \n** Reference:\n***\n\n* 2007-01-19\n** Speaker: 崔愷文\n** Topic: \n** Paper: None\n** Abstract: \n** Reference:\n***\n