{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:56Z","timestamp":1780822196776,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384235","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"1279-1292","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Three-in-a-tree in near linear time"],"prefix":"10.1145","author":[{"given":"Kai-Yuan","family":"Lai","sequence":"first","affiliation":[{"name":"National Taiwan University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsueh-I","family":"Lu","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.006"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.004"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.017"},{"key":"e_1_3_2_1_5_1","volume-title":"Les probl\u00e8mes de coloration en th\u00e9orie des graphes","author":"Berge C.","year":"1960","unstructured":"C. Berge . Les probl\u00e8mes de coloration en th\u00e9orie des graphes . Publications de l\u2019Institut de statistique de l\u2019Universit\u00e9 de Paris , 9:123\u2013160, 1960 . C. Berge. Les probl\u00e8mes de coloration en th\u00e9orie des graphes. Publications de l\u2019Institut de statistique de l\u2019Universit\u00e9 de Paris, 9:123\u2013160, 1960."},{"key":"e_1_3_2_1_6_1","first-page":"114","article-title":"F\u00e4rbung von Graphen deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universit\u00e4t Halle-Wittenberg","volume":"10","author":"Berge C.","year":"1961","unstructured":"C. Berge . F\u00e4rbung von Graphen deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universit\u00e4t Halle-Wittenberg , Mathematisch-Naturwissenschaftliche Reihe , 10 : 114 \u2013 115 , 1961 . C. Berge. F\u00e4rbung von Graphen deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universit\u00e4t Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, 10:114\u2013115, 1961.","journal-title":"Mathematisch-Naturwissenschaftliche Reihe"},{"key":"e_1_3_2_1_7_1","unstructured":"C. Berge. Graphs. North-Holland Amsterdam New York 1985. C. Berge. Graphs. North-Holland Amsterdam New York 1985."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90098-M"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90357-L"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.02.004"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.02.001"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.11.003"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/060672613"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20040"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375720"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2334-4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.07.005"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1131301"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90049-8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646136"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379204.1379208"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379851.1379853"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10006"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10045"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010444540X"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238177"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.07.027"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.10.001"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.009"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-009-0867-3"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01961541"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.21711\/231766362015\/rmc4410","article-title":"The k-in-a-tree problem for chordal graphs","volume":"44","author":"dos Santos V. F.","year":"2015","unstructured":"V. F. dos Santos , V. G. da Silva , and J. L. Szwarcfiter . The k-in-a-tree problem for chordal graphs . Matem\u00e1tica Contempor\u00e2nea , 44 : 1 \u2013 10 , 2015 . https:\/\/mc.sbm.org.br\/volumes\/volume-44\/. V. F. dos Santos, V. G. da Silva, and J. L. Szwarcfiter. The k-in-a-tree problem for chordal graphs. Matem\u00e1tica Contempor\u00e2nea, 44:1\u201310, 2015. https:\/\/mc.sbm.org.br\/volumes\/volume-44\/.","journal-title":"Matem\u00e1tica Contempor\u00e2nea"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9468-z"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-018-1925-5"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_14"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/140963200"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44541-2_8"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/23005.31330"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.12.005"},{"key":"e_1_3_2_1_47_1","volume-title":"Department of Computer Science and Information Engineering","author":"Lai K.-Y.","year":"2018","unstructured":"K.-Y. Lai . Sapling detection. Master\u2019s thesis , Department of Computer Science and Information Engineering , National Taiwan University , 2018 . K.-Y. Lai. Sapling detection. Master\u2019s thesis, Department of Computer Science and Information Engineering, National Taiwan University, 2018."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.015"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.06.005"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104442522"},{"issue":"2","key":"e_1_3_2_1_53_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Nesetril J.","year":"1985","unstructured":"J. Nesetril and S. Poljak . On the complexity of the subgraph problem . Commentationes Mathematicae Universitatis Carolinae , 26 ( 2 ): 415 \u2013 419 , 1985 . http:\/\/eudml.org\/doc\/17394. J. Nesetril and S. Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415\u2013419, 1985. http:\/\/eudml.org\/doc\/17394.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.07.010"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1033"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.07.004"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20405"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.06.002"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.3138\/9781487584863"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9470-5"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.2298\/AADM100812027V"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.126"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384235","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":66,"alternative-id":["10.1145\/3357713.3384235","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384235","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}