{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:22Z","timestamp":1781077942220,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":65,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2017\/27\/N\/ST6\/02719"],"award-info":[{"award-number":["2017\/27\/N\/ST6\/02719"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316390","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"733-743","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing quartet distance is equivalent to counting 4-cycles"],"prefix":"10.1145","author":[{"given":"Bart\u0142omiej","family":"Dudek","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014.  Amir Abboud and Virginia Vassilevska Williams. 2014."},{"key":"e_1_3_2_1_2_1","unstructured":"Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS. IEEE Computer Society 434\u2013443.  Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS. IEEE Computer Society 434\u2013443."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-001-8006-8"},{"key":"e_1_3_2_1_5_1","unstructured":"Noga Alon Humberto Naves and Benny Sudakov. 2016.  Noga Alon Humberto Naves and Benny Sudakov. 2016."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"On the Maximum Quartet Distance between Phylogenetic Trees. SIAM J. Discrete Math. 30 2 (2016) 718\u2013735.  On the Maximum Quartet Distance between Phylogenetic Trees. SIAM J. Discrete Math. 30 2 (2016) 718\u2013735.","DOI":"10.1137\/15M1041754"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_2_1_8_1","unstructured":"Stephen Alstrup Jacob Holm Kristian de Lichtenberg and Mikkel Thorup. 2005.  Stephen Alstrup Jacob Holm Kristian de Lichtenberg and Mikkel Thorup. 2005."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_2_1_10_1","unstructured":"Hans-J\u00fcrgen Bandelt and Andreas Dress. 1986.  Hans-J\u00fcrgen Bandelt and Andreas Dress. 1986."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.08.027"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00235-2"},{"key":"e_1_3_2_1_14_1","unstructured":"Vincent Berry Tao Jiang Paul E. Kearney Ming Li and Todd Wareham. 1999.  Vincent Berry Tao Jiang Paul E. Kearney Ming Li and Todd Wareham. 1999."},{"key":"e_1_3_2_1_15_1","volume-title":"ESA (Lecture Notes in Computer Science)","author":"Cleaning Quartet"},{"key":"e_1_3_2_1_16_1","unstructured":"Philip Bille Inge Li G\u00f8rtz Gad M. Landau and Oren Weimann. 2015.  Philip Bille Inge Li G\u00f8rtz Gad M. Landau and Oren Weimann. 2015."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.012"},{"key":"e_1_3_2_1_18_1","unstructured":"Gerth St\u00f8lting Brodal Rolf Fagerberg Thomas Mailund Christian N. S. Pedersen and Andreas Sand. 2013.  Gerth St\u00f8lting Brodal Rolf Fagerberg Thomas Mailund Christian N. S. Pedersen and Andreas Sand. 2013."},{"key":"e_1_3_2_1_19_1","volume-title":"SODA","author":"Efficient","year":"1814"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_62"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1065-y"},{"key":"e_1_3_2_1_22_1","unstructured":"David Bryant John Tsang Paul E. Kearney and Ming Li. 2000. Computing the quartet distance between evolutionary trees. In SODA. ACM\/SIAM 285\u2013286.   David Bryant John Tsang Paul E. Kearney and Ming Li. 2000. Computing the quartet distance between evolutionary trees. In SODA. ACM\/SIAM 285\u2013286."},{"key":"e_1_3_2_1_23_1","volume-title":"Mathematics the the Archeological and Historical Sciences","author":"Buneman Peter"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11557067_7"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Chris Christiansen Thomas Mailund Christian N. S. Pedersen Martin Randers and Martin Stig Stissing. 2006. Fast calculation of the quartet distance between trees of arbitrary degrees. Algorithms for Molecular Biology 1 (2006).  Chris Christiansen Thomas Mailund Christian N. S. Pedersen Martin Randers and Martin Stig Stissing. 2006. Fast calculation of the quartet distance between trees of arbitrary degrees. Algorithms for Molecular Biology 1 (2006).","DOI":"10.1186\/1748-7188-1-16"},{"key":"e_1_3_2_1_26_1","unstructured":"Douglas E. Critchlow Dennis K. Pearl and Chunlin Qian. 1996.  Douglas E. Critchlow Dennis K. Pearl and Chunlin Qian. 1996."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"The Triples Distance for Rooted Bifurcating Phylogenetic Trees. Systematic Biology 45 3 (1996) 323\u2013334.  The Triples Distance for Rooted Bifurcating Phylogenetic Trees. Systematic Biology 45 3 (1996) 323\u2013334.","DOI":"10.1093\/sysbio\/45.3.323"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055459"},{"key":"e_1_3_2_1_29_1","unstructured":"Annette J. Dobson. 1975.  Annette J. Dobson. 1975."},{"key":"e_1_3_2_1_30_1","volume-title":"Combinatorial Mathematics III","author":"Comparing"},{"key":"e_1_3_2_1_31_1","unstructured":"Bart\u0142omiej Dudek and Pawe\u0142 Gawrychowski. 2018. Computing Quartet Distance is Equivalent to Counting 4-Cycles. CoRR abs\/1811.06244 (2018).  Bart\u0142omiej Dudek and Pawe\u0142 Gawrychowski. 2018. Computing Quartet Distance is Equivalent to Counting 4-Cycles. CoRR abs\/1811.06244 (2018)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2307\/2413326"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC. ACM 296\u2013303.  Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC. ACM 296\u2013303.","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_34_1","unstructured":"R. D. Gray A. J. Drummond and S. J. Greenhill. 2009.  R. D. Gray A. J. Drummond and S. J. Greenhill. 2009."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Language Phylogenies Reveal Expansion Pulses and Pauses in Pacific Settlement. Science 323 5913 (2009) 479\u2013483.  Language Phylogenies Reveal Expansion Pulses and Pauses in Pacific Settlement. Science 323 5913 (2009) 479\u2013483.","DOI":"10.1126\/science.1166858"},{"key":"e_1_3_2_1_36_1","unstructured":"Dan Gusfield. 1997.  Dan Gusfield. 1997."},{"key":"e_1_3_2_1_37_1","unstructured":"Algorithms on Strings Trees and Sequences - Computer Science and Computational Biology. Cambridge University Press.   Algorithms on Strings Trees and Sequences - Computer Science and Computational Biology. Cambridge University Press."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.10.002"},{"key":"e_1_3_2_1_39_1","volume-title":"AlCoB (Lecture Notes in Computer Science)","author":"Jansson Jesper"},{"key":"e_1_3_2_1_40_1","volume-title":"Orchestrating Quartets: Approximation and Data Correction","author":"Jiang Tao","year":"1998"},{"key":"e_1_3_2_1_41_1","unstructured":"Katherine St. John Tandy J. Warnow Bernard M. E. Moret and Lisa Vawter. 2003.  Katherine St. John Tandy J. Warnow Bernard M. E. Moret and Lisa Vawter. 2003."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00049-X"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-968X.2005.00149.x"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(81)90043-2"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"D. F. Robinson and L. R. Foulds. 1979. Comparison of weighted labelled trees. In Combinatorial Mathematics VI A. F. Horadam and W. D. Wallis (Eds.). Springer Berlin Heidelberg 119\u2013126.  D. F. Robinson and L. R. Foulds. 1979. Comparison of weighted labelled trees. In Combinatorial Mathematics VI A. F. Horadam and W. D. Wallis (Eds.). Springer Berlin Heidelberg 119\u2013126.","DOI":"10.1007\/BFb0102690"},{"key":"e_1_3_2_1_46_1","unstructured":"N. Saitou and M. Nei. 1987.  N. Saitou and M. Nei. 1987."},{"key":"e_1_3_2_1_47_1","unstructured":"The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution 4 4 (1987) 406\u2013425.  The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution 4 4 (1987) 406\u2013425."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Andreas Sand Gerth St\u00f8lting Brodal Rolf Fagerberg Christian N. S. Pedersen and Thomas Mailund. 2013. A practical O (n log 2 n) time algorithm for computing the triplet distance on binary trees. BMC Bioinformatics 14 S-2 (2013) S18.  Andreas Sand Gerth St\u00f8lting Brodal Rolf Fagerberg Christian N. S. Pedersen and Thomas Mailund. 2013. A practical O (n log 2 n) time algorithm for computing the triplet distance on binary trees. BMC Bioinformatics 14 S-2 (2013) S18.","DOI":"10.1186\/1471-2105-14-S2-S18"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Andreas Sand Morten Kragelund Holt Jens Johansen Rolf Fagerberg Gerth St\u00f8lting Brodal Christian N. S. Pedersen and Thomas Mailund. 2013. Algorithms for Computing the Triplet Quartet Distances for Binary General Trees. In Biology.  Andreas Sand Morten Kragelund Holt Jens Johansen Rolf Fagerberg Gerth St\u00f8lting Brodal Christian N. S. Pedersen and Thomas Mailund. 2013. Algorithms for Computing the Triplet Quartet Distances for Binary General Trees. In Biology.","DOI":"10.3390\/biology2041189"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.133"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/11086964X"},{"key":"e_1_3_2_1_52_1","first-page":"126","article-title":"Distributions of Tree Comparison Metrics\u2014Some New Results","volume":"42","author":"Steel Mike A.","year":"1993","journal-title":"Systematic Biology"},{"key":"e_1_3_2_1_53_1","unstructured":"Martin Stig Stissing Christian N. S. Pedersen Thomas Mailund Gerth St\u00f8lting Brodal and Rolf Fagerberg. 2007.  Martin Stig Stissing Christian N. S. Pedersen Thomas Mailund Gerth St\u00f8lting Brodal and Rolf Fagerberg. 2007."},{"key":"e_1_3_2_1_54_1","volume-title":"APBC (Advances in Bioinformatics and Computational Biology)","author":"Quartet Distance Between Evolutionary Computing"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a025664"},{"key":"e_1_3_2_1_56_1","unstructured":"Robert S. Walker S\u00f8ren Wichmann Thomas Mailund and Curtis J. Atkisson. 2012.  Robert S. Walker S\u00f8ren Wichmann Thomas Mailund and Curtis J. Atkisson. 2012."},{"key":"e_1_3_2_1_57_1","unstructured":"Cultural Phylogenetics of the Tupi Language Family in Lowland South America. PLOS ONE 7 4 (04 2012) 1\u20139.  Cultural Phylogenetics of the Tupi Language Family in Lowland South America. PLOS ONE 7 4 (04 2012) 1\u20139."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(78)90137-6"},{"key":"e_1_3_2_1_59_1","unstructured":"Virginia Vassilevska Williams. 2012.  Virginia Vassilevska Williams. 2012."},{"key":"e_1_3_2_1_60_1","unstructured":"Multiplying matrices faster than coppersmith-winograd. In STOC. ACM 887\u2013898.  Multiplying matrices faster than coppersmith-winograd. In STOC. ACM 887\u2013898."},{"key":"e_1_3_2_1_61_1","unstructured":"Virginia Vassilevska Williams. 2014.  Virginia Vassilevska Williams. 2014."},{"key":"e_1_3_2_1_62_1","volume-title":"International Congress of Mathematicians (ICM).","author":"On"},{"key":"e_1_3_2_1_63_1","unstructured":"Virginia Vassilevska Williams Joshua R. Wang Richard Ryan Williams and Huacheng Yu. 2015. Finding Four-Node Subgraphs in Triangle Time. In SODA. SIAM 1671\u20131680.   Virginia Vassilevska Williams Joshua R. Wang Richard Ryan Williams and Huacheng Yu. 2015. Finding Four-Node Subgraphs in Triangle Time. In SODA. SIAM 1671\u20131680."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194274133"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316390","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316390"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":65,"alternative-id":["10.1145\/3313276.3316390","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316390","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}