請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86005
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Yung-Chung Chiu | en |
dc.contributor.author | 邱允中 | zh_TW |
dc.date.accessioned | 2023-03-19T23:32:31Z | - |
dc.date.copyright | 2022-09-23 | |
dc.date.issued | 2022 | |
dc.date.submitted | 2022-09-19 | |
dc.identifier.citation | [1] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzazewski, and P. D. Seymour. Induced subgraphs of bounded treewidth and the container method. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 1948–1964, 2021. doi:10.1137/1.9781611976465.116. [2] J. Alman and V. Vassilevska Williams. A refined laser method and faster matrix multiplication. In D. Marx, editor, Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 522–539, 2021. doi:10.1137/1.9781611976465.32. [3] N. Alon, R. Yuster, and U. Zwick. Color-coding. Journal of the ACM, 42(4):844–856, 1995.doi:10.1145/210332.210337. [4] C. Berge. Les problèmes de coloration en théorie des graphes. Publications de l’Institut de statistique de l’Université de Paris, 9:123–160, 1960. [5] C. Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, 10:114–115, 1961. [6] C. Berge. Graphs. North-Holland, Amsterdam, New York, 1985. [7] E. Berger, P. D. Seymour, and S. Spirkl. Finding an induced path that is not a shortest path. Discrete Mathematics, 344(7):112398.1–112398.6, 2021. doi:10.1016/j.disc.2021.112398. [8] D. Bienstock. On the complexity of testing for odd holes and induced odd paths. Discrete Mathematics, 90(1):85–92, 1991. doi:10.1016/0012-365X(91)90098-M, see [9] for corrigendum. [9] D. Bienstock. Corrigendum to: D. Bienstock, “On the complexity of testing for odd holes and induced odd paths” Discrete Mathematics 90 (1991) 85–92. Discrete Mathematics, 102(1):109, 1992. doi:10.1016/0012-365X(92)90357-L. [10] N. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory, 1736-1936. Oxford University Press, 1986. [11] A. Björklund, T. Husfeldt, and P. Kaski. The shortest even cycle problem is tractable. In S. Leonardi and A. Gupta, editors, Proceedings of the 54th Annual Symposium on Theory of Computing, pages 117–130, 2022. doi:10.1145/3519935.3520030. [12] H.-C. Chang and H.-I. Lu. Computing the girth of a planar graph in linear time. SIAM Journal on Computing, 42(3):1077–1094, 2013. doi:10.1137/110832033. [13] H.-C. Chang and H.-I. Lu. A faster algorithm to recognize even-hole-free graphs. Journal of Combinatorial Theory, Series B, 113:141–161, 2015. doi:10.1016/j.jctb.2015.02.001. [14] Y. Chen and J. Flum. On parameterized path and chordless path problems. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pages 250–263, 2007. doi:10.1109/CCC.2007.21. [15] H.-T. Cheong and H.-I. Lu. Finding a shortest even hole in polynomial time. Journal of Graph Theory, 99(3):425–434, 2022. doi:10.1002/jgt.22748. [16] Y.-C. Chiu and H.-I. Lu. Blazing a trail via matrix multiplications: A faster algorithm for non-shortest induced paths. In P. Berenbrink and B. Monmege, editors, Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, LIPIcs 219, pages 23:1–23:16, 2022. doi:10.4230/LIPIcs.STACS.2022.23. [17] M. Chudnovsky, G. Cornuéjols, X. Liu, P. D. Seymour, and K. Vušković. Recognizing Berge graphs. Combinatorica, 25(2):143–186, 2005. doi:10.1007/s00493-005-0012-8. [18] M. Chudnovsky, K.-i. Kawarabayashi, and P. Seymour. Detecting even holes. Journal of Graph Theory, 48(2):85–111, 2005. doi:10.1002/jgt.20040. [19] M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. On the maximum weight independent set problem in graphs without induced cycles of length at least five. SIAM Journal on Discrete Mathematics, 34(2):1472–1483, 2020. doi:10.1137/19M1249473. [20] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164(1):51–229, 2006. doi:10.4007/annals.2006.164.51. [21] M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas. Progress on perfect graphs. Mathematical Programming, 97(1-2):405–422, 2003. doi:10.1007/s10107-003-0449-8. [22] M. Chudnovsky, A. Scott, and P. Seymour. Detecting a long odd hole. Combinatorica, 41(1):1–30, 2021. doi:10.1007/s00493-020-4301-z. [23] M. Chudnovsky, A. Scott, and P. Seymour. Finding a shortest odd hole. ACM Transactions on Algorithms, 17(2):13.1–13.21, 2021. doi:10.1145/3447869. [24] M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Detecting an odd hole. Journal of the ACM, 67(1):5.1–5.12, 2020. doi:10.1145/3375720. [25] M. Chudnovsky and P. Seymour. The three-in-a-tree problem. Combinatorica, 30(4):387–417, 2010. doi:10.1007/s00493-010-2334-4. [26] M. Chudnovsky and P. D. Seymour. Even pairs in Berge graphs. Journal of Combinatorial Theory, Series B, 99(2):370–377, 2009. doi:10.1016/j.jctb.2008.08.002. [27] M. Chudnovsky and V. Sivaraman. Odd holes in bull-free graphs. SIAM Journal on Discrete Mathematics, 32(2):951–955, 2018. doi:10.1137/17M1131301. [28] V. Chvátal and N. Sbihi. Bull-free berge graphs are perfect. Graphs and Combinatorics, 3(1):127–139, 1987. doi:10.1007/BF01788536. [29] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Finding an even hole in a graph. In Proceedings of the 38th Symposium on Foundations of Computer Science, pages 480–485, 1997. doi:10.1109/SFCS.1997.646136. [30] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even and odd holes in cap-free graphs. Journal of Graph Theory, 30(4):289–308, 1999. doi:10.1002/(SICI)1097-0118(199904)30:4<289::AID-JGT4>3.0.CO;2-3. [31] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even-hole-free graphs Part I: Decomposition theorem. Journal of Graph Theory, 39(1):6–49, 2002. doi:10.1002/jgt.10006. [32] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even-hole-free graphs Part II: Recognition algorithm. Journal of Graph Theory, 40(4):238–266, 2002. doi:10.1002/jgt.10045. [33] M. Conforti, G. Cornuéjols, X. Liu, K. Vušković, and G. Zambelli. Odd hole recognition in graphs of bounded clique size. SIAM Journal on Discrete Mathematics, 20(1):42–48, 2006. doi:10.1137/S089548010444540X. [34] M. Conforti, G. Cornuéjols, and M. R. Rao. Decomposition of balanced matrices. Journal of Combinatorial Theory, Series B, 77(2):292–406, 1999. doi:10.1006/jctb.1999.1932. [35] M. Conforti, G. Cornuéjols, and K. Vušković. Square-free perfect graphs. Journal of Combinatorial Theory, Series B, 90(2):257–307, 2004. doi:10.1016/j.jctb.2003.08.003. [36] L. Cook, J. Horsfield, M. Preissmann, C. Robin, P. Seymour, N. L. D. Sintiari, N. Trotignon, and K. Vušković. Graphs with all holes the same length. arXiv, 2021. doi:10.48550/arxiv.2110.09970. [37] L. Cook and P. D. Seymour. Detecting a long even hole. European Journal of Combinatorics, 104:103537, 2022. doi:10.1016/j.ejc.2022.103537. [38] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, 1990. doi:10.1016/S0747-7171(08)80013-2. [39] G. Cornuéjols, X. Liu, and K. Vušković. A polynomial algorithm for recognizing perfect graphs. In Proceedings of the 44th Symposium on Foundations of Computer Science, pages 20–27, 2003. doi:10.1109/SFCS.2003.1238177. [40] M. V. G. da Silva and K. Vušković. Decomposition of even-hole-free graphs with star-cutsets and 2-joins. Journal of Combinatorial Theory, Series B, 103(1):144–183, 2013. doi:10.1016/j.jctb.2012.10.001. [41] S. Dahlgaard, M. B. T. Knudsen, and M. Stöckel. Finding even cycles faster via capped k-walks. In H. Hatami, P. McKenzie, and V. King, editors, Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 112–120. ACM, 2017. doi:10.1145/3055399.3055459. [42] M. Dalirrooyfard and V. Vassilevska Williams. Induced cycles and paths are harder than you think. In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science, 2022, to appear. doi:10.48550/arXiv.2209.01873. [43] M. Dalirrooyfard, T. D. Vuong, and V. Vassilevska Williams. Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Symposium on Theory of Computing, pages 1167–1178, 2019. doi:10.1145/3313276.3316329. [44] D. Eppstein. Finding the k shortest paths. SIAM Journal on Computing, 28(2):652–673, 1998. doi:10.1137/S0097539795290477. [45] H. Everett, C. M. H. de Figueiredo, C. L. Sales, F. Maffray, O. Porto, and B. A. Reed. Path parity and perfection. Discrete Mathematics, 165-166:233–252, 1997. doi:10.1016/S0012-365X(96)00174-4. [46] M. R. Fellows, J. Kratochvíl, M. Middendorf, and F. Pfeiffer. The complexity of induced minors and related problems. Algorithmica, 13(3):266–282, 1995. doi:10.1007/BF01190507. [47] J. Fonlupt and J. Uhry. Transformations which preserve perfectness and H-perfectness of graphs. In A. Bachem, M. Grötschel, and B. Korte, editors, Bonn Workshop on Combinatorial Optimization, volume 66 of North-Holland Mathematics Studies, pages 83–95. North-Holland, 1982. doi:10.1016/S0304-0208(08)72445-9. [48] Z. Galil and O. Margalit. Witnesses for boolean matrix multiplication and for transitive closure. Journal of Complexity, 9(2):201–221, 1993. doi:10.1006/jcom.1993.1014. [49] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. [50] S. Gaspers, S. Huang, and D. Paulusma. Colouring square-free graphs without long induced paths. In R. Niedermeier and B. Vallée, editors, Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, LIPIcs 96, pages 35.1–35.15, 2018. doi:10.4230/LIPIcs.STACS.2018.35. [51] E. D. Giacomo, G. Liotta, and T. Mchedlidze. Lower and upper bounds for long induced paths in 3-connected planar graphs. Theoretical Computer Science, 636:47–55, 2016. doi:10.1016/j.tcs.2016.04.034. [52] P. A. Golovach, D. Paulusma, and E. J. van Leeuwen. Induced disjoint paths in AT-free graphs. In F. V. Fomin and P. Kaski, editors, Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, Lecture Notes in Computer Science 7357, pages 153–164, 2012. doi:10.1007/978-3-642-31155-0_14. [53] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. [54] R. Haas and M. Hoffmann. Chordless paths through three vertices. Theoretical Computer Science, 351(3):360–371, 2006. doi:10.1016/j.tcs.2005.10.021. [55] C. T. Hoàng, M. Kaminski, J. Sawada, and R. Sritharan. Finding and listing induced paths and cycles. Discrete Applied Mathematics, 161(4-5):633–641, 2013. doi:10.1016/j.dam.2012.01.024. [56] J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723–760, July 2001. doi:10.1145/502090.502095. [57] W.-L. Hsu. Recognizing planar perfect graphs. Journal of the ACM, 34(2):255–288, 1987. doi:10.1145/23005.31330. [58] A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413–423, 1978. doi:10.1137/0207033. [59] L. Jaffke, O.-j. Kwon, and J. A. Telle. Mim-width I. induced path problems. Discrete Applied Mathematics, 278:153–168, 2020. doi:10.1016/j.dam.2019.06.026. [60] D. S. Johnson. The NP-completeness column. ACM Transactions on Algorithms, 1(1):160–176, 2005. doi:10.1145/1077464.1077476. [61] M. Kaminski and N. Nishimura. Finding an induced path of given parity in planar graphs in polynomial time. In Y. Rabani, editor, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 656–670, 2012. doi:10.1137/1.9781611973099.55. [62] K. Kawarabayashi, Y. Kobayashi, and B. A. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012. doi:10.1016/j.jctb.2011.07.004. [63] L. G. Khachiyan. A polynomial algorithm in linear programming. In Doklady Akademii Nauk, volume 244, pages 1093–1096. Russian Academy of Sciences, 1979. [64] M. Kriesell. Induced paths in 5-connected graphs. Journal of Graph Theory, 36(1):52–58, 2001. doi:10.1002/1097-0118(200101)36:1<52::AID-JGT5>3.0.CO;2-N. [65] K.-Y. Lai, H.-I. Lu, and M. Thorup. Three-in-a-tree in near linear time. In Proccedings of the 52nd Annual ACM Symposium on Theory of Computing, pages 1279–1292, 2020. doi:10.1145/3357713.3384235. [66] F. Le Gall. Powers of tensors and fast matrix multiplication. In K. Nabeshima, K. Nagasaka, F. Winkler, and Á. Szántó, editors, Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 296–303, 2014. doi:10.1145/2608628.2608664. [67] W. Liu and N. Trotignon. The k-in-a-tree problem for graphs of girth at least k. Discrete Applied Mathematics, 158(15):1644–1649, 2010. doi:10.1016/j.dam.2010.06.005. [68] L. Lovász. A characterization of perfect graphs. Journal of Combinatorial Theory, Series B, 13(2):95–98, 1972. doi:10.1016/0095-8956(72)90045-7. [69] L. Lovász. Graph minor theory. American Mathematical Society. Bulletin. New Series, 43(1):75–86, 2006. doi:10.1090/S0273-0979-05-01088-8. [70] W. McCuaig. Pólya’s permanent problem. Electronic Journal of Combinatorics, 11(1), 2004. doi:10.37236/1832. [71] H. Meyniel. A new property of critical imperfect graphs and some consequences. European Journal of Combinatorics, 8(3):313–316, 1987. doi:10.1016/S0195-6698(87)80037-9. [72] O. Porto. Even induced cycles in planar graphs. In Proceedings of the 1st Latin American Symposium on Theoretical Informatics, pages 417–429, 1992. doi:10.1007/BFb0023845. [73] M. Radovanovic, N. Trotignon, and K. Vušković. The (theta, wheel)-free graphs part IV: induced paths and cycles. Journal of Combinatorial Theory, Series B, 146:495–531, 2021. doi:10.1016/j.jctb.2020.06.002. [74] B. A. Reed. A semi-strong perfect graph theorem. Journal of Combinatorial Theory, Series B, 43(2):223–240, 1987. doi:10.1016/0095-8956(87)90022-0. [75] N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983. doi:10.1016/0095-8956(83)90079-5. [76] N. Robertson and P. D. Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984. doi:10.1016/0095-8956(84)90013-3. [77] N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309–322, 1986. doi:10.1016/0196-6774(86)90023-4. [78] N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4. [79] N. Robertson and P. D. Seymour. Graph minors. VI. Disjoint paths across a disc. Journal of Combinatorial Theory, Series B, 41(1):115–138, 1986. doi:10.1016/0095-8956(86)90031-6. [80] N. Robertson and P. D. Seymour. Graph minors. VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B, 45(2):212–254, 1988. doi:10.1016/0095-8956(88)90070-6. [81] N. Robertson and P. D. Seymour. Graph minors. IV. Tree-width and well-quasi-ordering. Journal of Combinatorial Theory, Series B, 48(2):227–254, 1990. doi:10.1016/0095-8956(90)90120-O. [82] N. Robertson and P. D. Seymour. Graph minors. IX. Disjoint crossed paths. Journal of Combinatorial Theory, Series B, 49(1):40–77, 1990. doi:10.1016/0095-8956(90)90063-6. [83] N. Robertson and P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces. Journal of Combinatorial Theory, Series B, 48(2):255–288, 1990. doi:10.1016/0095-8956(90)90121-F. [84] N. Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991. doi:10.1016/0095-8956(91)90061-N. [85] N. Robertson and P. D. Seymour. Graph minors. XI. Circuits on a surface. Journal of Combinatorial Theory, Series B, 60(1):72–106, 1994. doi:10.1006/jctb.1994.1007. [86] N. Robertson and P. D. Seymour. Graph minors. XII. Distance on a surface. Journal of Combinatorial Theory, Series B, 64(2):240–272, 1995. doi:10.1006/jctb.1995.1034. [87] N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995. doi:10.1006/jctb.1995.1006. [88] N. Robertson and P. D. Seymour. Graph minors. XIV. Extending an embedding. Journal of Combinatorial Theory, Series B, 65(1):23–50, 1995. doi:10.1006/jctb.1995.1042. [89] N. Robertson and P. D. Seymour. Graph minors: XV. Giant steps. Journal of Combinatorial Theory, Series B, 68(1):112–148, 1996. doi:10.1006/jctb.1996.0059. [90] N. Robertson and P. D. Seymour. Graph minors: XVII. Taming a vortex. Journal of Combinatorial Theory, Series B, 77(1):162–210, 1999. doi:10.1006/jctb.1999.1919. [91] N. Robertson and P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003. doi:10.1016/S0095-8956(03)00042-X. [92] N. Robertson and P. D. Seymour. Graph minors. XVIII. Tree-decompositions and well-quasi-ordering. Journal of Combinatorial Theory, Series B, 89(1):77–108, 2003. doi:10.1016/S0095-8956(03)00067-4. [93] N. Robertson and P. D. Seymour. Graph minors. XIX. Well-quasi-ordering on a surface. Journal of Combinatorial Theory, Series B, 90(2):325–385, 2004. doi:10.1016/j.jctb.2003.08.005. [94] N. Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004. doi:10.1016/j.jctb.2004.08.001. [95] N. Robertson and P. D. Seymour. Graph minors. XXI. Graphs with unique linkages. Journal of Combinatorial Theory, Series B, 99(3):583–616, 2009. doi:10.1016/j.jctb.2008.08.003. [96] N. Robertson and P. D. Seymour. Graph minors XXIII. Nash-Williams’ immersion conjecture. Journal of Combinatorial Theory, Series B, 100(2):181–205, 2010. doi:10.1016/j.jctb.2009.07.003. [97] N. Robertson and P. D. Seymour. Graph minors. XXII. Irrelevant vertices in linkage problems. Journal of Combinatorial Theory, Series B, 102(2):530–563, 2012. doi:10.1016/j.jctb.2007.12.007. [98] N. Robertson, P. D. Seymour, and R. Thomas. Permanents, Pfaffian orientations, and even directed circuits. Annals of Mathematics, 150(3):929–975, 1999. doi:10.2307/121059. [99] D. Rose, R. Tarjan, and G. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266–283, 1976. doi:10.1137/0205021. [100] R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566–579, 1984. doi:10.1137/0213035, see [101] for addendum. [101] R. E. Tarjan and M. Yannakakis. Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 14(1):254–255, 1985. doi:10.1137/0214020. [102] N. Trotignon. Perfect graphs, page 137–160. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2015. [103] V. Vassilevska Williams. Multiplying matrices faster than Coppersmith–Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 887–898, 2012. doi:10.1145/2213977.2214056. [104] V. V. Williams and R. R. Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM, 65(5):27:1–27:38, 2018. doi:10.1145/3186893. [105] R. Yuster and U. Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathematics, 10(2):209–222, 1997. doi:10.1137/S0895480194274133. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86005 | - |
dc.description.abstract | 判斷一張圖中是否包含某種導出子圖,在圖論以及演算法領域的許多重要成果都扮演了重要角色。其中一個具有高度代表性的例子是「完美圖的辨識問題」,也就是判定一張圖是否符合「每個導出子圖中,最大團的頂點數都等於該導出子圖的著色數。」2006 年 Chudnovsky、Robertson、Seymour 以及 Thomas 明了「完美圖定理」這個獲得 2009 年 Fulkerson Prize 殊榮的成果,解決 Berge 在 1960 年留下的猜想,確認「一張圖是完美圖若且唯若它和它的補圖都不包含任何奇洞」,其中一張圖的奇洞是該圖的一個長度至少五且為奇數的導出環。根據這個定理,Chudnovsky、Cornuéjols、Liu、Seymour 以及 Vušković提出了一個時間複雜度為 O(n^9) 演算法來辨認完美圖,其中 n 表示圖的節點數。在此篇論文中,我們改進了三個偵測/找一張有 n 節點的圖 G 的導出子圖的演算法。分別說明如下: 1. 是否存在一個多項式時間演算法來偵測「G 否包含奇洞」在長達數十年期間一直是無人能解的懸案。Chudnovsky、Scott、Seymour 以及 Spirkl 終於在 Journal of the ACM 2020年提出了第一個多項式時間偵測 G 的奇洞的演算法,時間複雜度為 O(n^9)。Lai、Lu以及 Thorup 之後在 ACM STOC 2020 進到 O(n^8),我們則進一步改進到 O(n^7),從而也把辨識完美圖的的時間複雜度改進到 O(n^7)。 2. Chudnovsky、Scott 以及 Seymour 在 ACM Transactions on Algorithms 2021 年提出了第一個多項式時間尋找 G 最短奇洞的演算法,時間複雜度為 O(n^14)。我們將其改進到O(n^13)。 3. Berger、Seymour 以及 Spirkl 在 Discrete Mathematics 2021 年提出了第一個尋找 G 給 定兩點之間非最短導出路徑的演算法,時間複雜度為 O(n^18)。我們將其大幅度改進 到 O(n^4.75)。這第三個成果已經發表在 Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)。 | zh_TW |
dc.description.abstract | An induced subgraph of an n-vertex graph G is a graph that can be obtained by deleting a set of vertices together with its incident edges from G. A hole of G is an induced cycle of G with length at least four. A hole is odd (respectively, even) if its number of edges is odd (respectively, even). Various classes of induced subgraphs are involved in the deepest results of graph theory and graph algorithms. A prominent example concerns the perfection of G that the chromatic number of each induced subgraph H of G equals the clique number of H. The seminal Strong Perfect Graph Theorem proved in 2006 by Chudnovsky, Robertson, Seymour, and Thomas, conjectured by Berge in 1960, confirms that the perfection of G can be determined by detecting odd holes in G and its complement. Based on the theorem, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković show in 2005 an O(n^9)-time algorithm for recognizing perfect graphs, which can be implemented to run in O(n^(6+ω)) time for the exponent ω < 2.373 of square-matrixmultiplication. We show the following improved algorithms for detecting or finding induced subgraphs in G. 1. The tractability of detecting odd holes in G was open for decades until the major breakthrough of Chudnovsky, Scott, Seymour, and Spirkl in 2020. Their O(n^9)-time algorithm is later implemented by Lai, Lu, and Thorup to run in O(n^8) time, leading to the best formerly known algorithm for recognizing perfect graphs. Our first result is an O(n^7)-time algorithm for detecting odd holes, immediately implying a state-of-the-art O(n^7)-time algorithm for recognizing perfect graphs. Finding an odd hole based on Lai et al.’s O(n^8)-time algorithm for detecting odd holes takes O(n^9) time. 2. Chudnovsky, Scott, and Seymour extend in 2021 the O(n^9)-time algorithms for detecting odd holes (2020) and recognizing perfect graphs (2005) into the first polynomial-time algorithm for obtaining a shortest odd hole in G, which runs in O(n^14) time. Our second result is an O(n^13)-time algorithm for finding a shortest odd hole in G. 3. For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. In 2021, Berger, Seymour, and Spirkl gave the previously only known polynomial-time algorithm, running in O(n^18) time, to find a uv-trail. We reduce the complexity to O˜(n^(2ω)) time, where the O˜ notation hides poly-logarithmic factors, leading to a largely improved O(n^4.75)-time algorithm. This third result has appeared in Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). | en |
dc.description.provenance | Made available in DSpace on 2023-03-19T23:32:31Z (GMT). No. of bitstreams: 1 U0001-1609202216453500.pdf: 715586 bytes, checksum: 3bfab85ef8857e8b878e51c5c7c98671 (MD5) Previous issue date: 2022 | en |
dc.description.tableofcontents | Acknowledgement i 摘要 ii Abstract iii 中文簡介 v Contents ix 1 Introduction 1 2 Recognizing Perfect Graphs via Detecting Odd Holes 7 2.1 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Proving Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Proving Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Proving Lemma 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 Proving Lemma 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.2 Proving Lemma 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 Proving Lemma 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.1 Proving Lemma 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.2 Proving Lemma 2.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Finding a Shortest Odd Hole 23 3.1 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Proving Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Proving Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Finding a Non-shortest Induced Path 31 4.1 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 A simpler algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 Conclusion 48 References 50 | |
dc.language.iso | en | |
dc.title | 三個導出子圖演算法——完美圖、最短奇洞、非最短路徑 | zh_TW |
dc.title | Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd Holes and Non-shortest Induced Paths | en |
dc.type | Thesis | |
dc.date.schoolyear | 110-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 顏嗣鈞(Hsu-chun Yen),陳和麟(Ho-Lin Chen),李彥寰(Yen-Huan Li) | |
dc.subject.keyword | 完美圖,導出子圖,奇洞,導出路徑,非最短路徑,動態資料結構, | zh_TW |
dc.subject.keyword | Perfect graph,Induced subgraph,Odd hole,Induced path,Non-shortest path,Dynamic data structure, | en |
dc.relation.page | 61 | |
dc.identifier.doi | 10.6342/NTU202203481 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2022-09-20 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
dc.date.embargo-lift | 2022-09-23 | - |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1609202216453500.pdf | 698.81 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。