{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:33:24Z","timestamp":1753889604342,"version":"3.40.3"},"publisher-location":"Cham","reference-count":51,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206238"},{"type":"electronic","value":"9783031206245"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20624-5_18","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"293-311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exact Learning of\u00a0Multitrees and\u00a0Almost-Trees Using Path Queries"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4740-1234","authenticated-orcid":false,"given":"Ramtin","family":"Afshar","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Bodwin, G., Rotenberg, E., St\u00f6ckel, M.: Graph reconstruction with a betweenness oracle. In: Ollinger, N., Vollmer, H. (eds.) 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, 17\u201320 February 2016, Orl\u00e9ans, France. LIPIcs, vol. 47, pp. 5:1\u20135:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.5","DOI":"10.4230\/LIPIcs.STACS.2016.5"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40273-9_1","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"P Afshani","year":"2013","unstructured":"Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K.G., Mehlhorn, K.: The query complexity of finding a hidden permutation. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 1\u201311. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40273-9_1"},{"key":"18_CR3","unstructured":"Afshar, R., Goodrich, M.T.: Exact learning of multitrees and almost-trees using path queries. 10.48550\/ARXIV.2208.04216, https:\/\/arxiv.org\/abs\/2208.04216"},{"key":"18_CR4","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Reconstructing binary trees in parallel. In: Scheideler, C., Spear, M. (eds.) SPAA 2020: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 15\u201317 July 2020, pp. 491\u2013492. ACM (2020). https:\/\/doi.org\/10.1145\/3350755.3400229","DOI":"10.1145\/3350755.3400229"},{"key":"18_CR5","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Reconstructing biological and digital phylogenetic trees in parallel. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, 7\u20139 September 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 173, pp. 3:1\u20133:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.3","DOI":"10.4230\/LIPIcs.ESA.2020.3"},{"key":"18_CR6","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Parallel network mapping algorithms. In: Agrawal, K., Azar, Y. (eds.) SPAA 2021: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6\u20138 July 2021, pp. 410\u2013413. ACM (2021). https:\/\/doi.org\/10.1145\/3409964.3461822","DOI":"10.1145\/3409964.3461822"},{"key":"18_CR7","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Mapping networks via parallel kth-hop traceroute queries. In: Berenbrink, P., Monmege, B. (eds.) 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, 15\u201318 March 2022, Marseille, France (Virtual Conference). LIPIcs, vol. 219, pp. 4:1\u20134:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.4","DOI":"10.4230\/LIPIcs.STACS.2022.4"},{"issue":"9","key":"18_CR8","first-page":"1488","volume":"76","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 76(9), 1488\u20131493 (1993)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-319-03841-4_30","volume-title":"Graph Drawing","author":"MJ Bannister","year":"2013","unstructured":"Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of crossing minimization of almost-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 340\u2013351. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03841-4_30"},{"issue":"3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1046\/j.1365-294x.2001.01216.x","volume":"10","author":"NH Barton","year":"2001","unstructured":"Barton, N.H.: The role of hybridization in evolution. Mol. Ecol. 10(3), 551\u2013568 (2001)","journal-title":"Mol. Ecol."},{"key":"18_CR11","unstructured":"Bello, K., Honorio, J.: Computationally and statistically efficient learning of causal Bayes nets using path queries. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018(December), pp. 3\u20138, 2018. Montr\u00e9al, Canada, pp. 10954\u201310964 (2018). https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/a0b45d1bb84fe1bedbb8449764c4d5d5-Abstract.html"},{"key":"18_CR12","doi-asserted-by":"publisher","unstructured":"Bernasconi, A., Damm, C., Shparlinski, I.E.: Circuit and decision tree complexity of some number theoretic problems. Inf. Comput. 168(2), 113\u2013124 (2001). https:\/\/doi.org\/10.1006\/inco.2000.3017","DOI":"10.1006\/inco.2000.3017"},{"key":"18_CR13","doi-asserted-by":"publisher","unstructured":"Bestagini, P., Tagliasacchi, M., Tubaro, S.: Image phylogeny tree reconstruction based on region selection. In: 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, Shanghai, China, 20\u201325 March 2016, pp. 2059\u20132063. IEEE (2016). https:\/\/doi.org\/10.1109\/ICASSP.2016.7472039","DOI":"10.1109\/ICASSP.2016.7472039"},{"issue":"9\u201310","key":"18_CR14","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1016\/j.artint.2010.02.003","volume":"174","author":"S Choi","year":"2010","unstructured":"Choi, S., Kim, J.H.: Optimal query complexity bounds for finding graphs. Artif. Intell. 174(9\u201310), 551\u2013569 (2010). https:\/\/doi.org\/10.1016\/j.artint.2010.02.003","journal-title":"Artif. Intell."},{"key":"18_CR15","doi-asserted-by":"publisher","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: Hartmanis, J. (ed.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 28\u201330 May 1986, Berkeley, California, USA, pp. 206\u2013219. ACM (1986). https:\/\/doi.org\/10.1145\/12130.12151","DOI":"10.1145\/12130.12151"},{"key":"18_CR16","doi-asserted-by":"publisher","unstructured":"Colombo, C., Lepage, F., Kopp, R., Gnaedinger, E.: Two SDN multi-tree approaches for constrained seamless multicast. In: Pop, F., Negru, C., Gonz\u00e1lez-V\u00e9lez, H., Rak, J. (eds.) 2018 IEEE International Conference on Computational Science and Engineering, CSE 2018, Bucharest, Romania, 29\u201331 October 2018, pp. 77\u201384. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/CSE.2018.00017","DOI":"10.1109\/CSE.2018.00017"},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/net.10085","volume":"42","author":"F Comellas","year":"2003","unstructured":"Comellas, F., Fiol, M.A., Gimbert, J., Mitjana, M.: The spectra of wrapped butterfly digraphs. Networks 42(1), 15\u201319 (2003). https:\/\/doi.org\/10.1002\/net.10085","journal-title":"Networks"},{"issue":"7","key":"18_CR18","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1016\/j.jvcir.2013.07.011","volume":"24","author":"Z Dias","year":"2013","unstructured":"Dias, Z., Goldenstein, S., Rocha, A.: Exploring heuristic and optimum branching algorithms for image phylogeny. J. Vis. Commun. Image Represent. 24(7), 1124\u20131134 (2013). https:\/\/doi.org\/10.1016\/j.jvcir.2013.07.011","journal-title":"J. Vis. Commun. Image Represent."},{"issue":"3","key":"18_CR19","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1109\/MMUL.2013.17","volume":"20","author":"Z Dias","year":"2013","unstructured":"Dias, Z., Goldenstein, S., Rocha, A.: Large-scale image phylogeny: tracing image ancestral relationships. IEEE Multim. 20(3), 58\u201370 (2013). https:\/\/doi.org\/10.1109\/MMUL.2013.17","journal-title":"IEEE Multim."},{"issue":"2","key":"18_CR20","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1109\/TIFS.2011.2169959","volume":"7","author":"Z Dias","year":"2012","unstructured":"Dias, Z., Rocha, A., Goldenstein, S.: Image phylogeny by minimal spanning trees. IEEE Trans. Inf. Forensics Secur. 7(2), 774\u2013788 (2012). https:\/\/doi.org\/10.1109\/TIFS.2011.2169959","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"18_CR21","doi-asserted-by":"publisher","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: From query complexity to computational complexity. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 1107\u20131116. ACM (2012). https:\/\/doi.org\/10.1145\/2213977.2214076","DOI":"10.1145\/2213977.2214076"},{"issue":"1","key":"18_CR22","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1006\/jagm.1997.0897","volume":"26","author":"LA Goldberg","year":"1998","unstructured":"Goldberg, L.A., Goldberg, P.W., Phillips, C.A., Sorkin, G.B.: Constructing computer virus phylogenies. J. Algorithms 26(1), 188\u2013208 (1998). https:\/\/doi.org\/10.1006\/jagm.1997.0897","journal-title":"J. Algorithms"},{"key":"18_CR23","doi-asserted-by":"publisher","unstructured":"Goodrich, M.T., Jacob, R., Sitchinava, N.: Atomic power in forks: a super-logarithmic lower bound for implementing butterfly networks in the nonatomic binary fork-join model. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2141\u20132153. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.128","DOI":"10.1137\/1.9781611976465.128"},{"key":"18_CR24","doi-asserted-by":"publisher","unstructured":"Heckerman, D., Meek, C., Cooper, G.: A Bayesian approach to causal discovery. In: Holmes, D.E., Jain, L.C. (eds.) Innovations in Machine Learning, vol. 194, pp. 1\u201328. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-33486-6_1","DOI":"10.1007\/3-540-33486-6_1"},{"issue":"5","key":"18_CR25","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/S0092-8240(89)80102-8","volume":"51","author":"JJ Hein","year":"1989","unstructured":"Hein, J.J.: An optimal algorithm to reconstruct trees from additive distance data. Bull. Math. Biol. 51(5), 597\u2013603 (1989)","journal-title":"Bull. Math. Biol."},{"key":"18_CR26","unstructured":"H\u00fcnermund, P., Bareinboim, E.: Causal inference and data fusion in econometrics. arXiv preprint arXiv:1912.09104 (2019)"},{"issue":"4","key":"18_CR27","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1257\/jel.20191597","volume":"58","author":"GW Imbens","year":"2020","unstructured":"Imbens, G.W.: Potential outcome and directed acyclic graph approaches to causality: relevance for empirical practice in economics. J. Econ. Lit. 58(4), 1129\u201379 (2020)","journal-title":"J. Econ. Lit."},{"issue":"1","key":"18_CR28","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0890-5401(88)90016-8","volume":"79","author":"A Itai","year":"1988","unstructured":"Itai, A., Rodeh, M.: The multi-tree approach to reliability in distributed networks. Inf. Comput. 79(1), 43\u201359 (1988). https:\/\/doi.org\/10.1016\/0890-5401(88)90016-8","journal-title":"Inf. Comput."},{"key":"18_CR29","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-40935-6_14","volume-title":"Algorithmic Learning Theory","author":"M Jagadish","year":"2013","unstructured":"Jagadish, M., Sen, A.: Learning a bounded-degree tree using separator queries. In: Jain, S., Munos, R., Stephan, F., Zeugmann, T. (eds.) ALT 2013. LNCS (LNAI), vol. 8139, pp. 188\u2013202. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40935-6_14"},{"key":"18_CR30","unstructured":"Janardhanan, M.V., Reyzin, L.: On learning a hidden directed graph with path queries. CoRR abs\/2002.11541 (2020). https:\/\/arxiv.org\/abs\/2002.11541"},{"issue":"6","key":"18_CR31","first-page":"809","volume":"6","author":"JH Ji","year":"2008","unstructured":"Ji, J.H., Park, S.H., Woo, G., Cho, H.G.: Generating pylogenetic tree of homogeneous source code in a plagiarism detection system. Int. J. Control Autom. Syst. 6(6), 809\u2013817 (2008)","journal-title":"Int. J. Control Autom. Syst."},{"key":"18_CR32","unstructured":"King, V., Zhang, L., Zhou, Y.: On the complexity of distance-based evolutionary tree reconstruction. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 12\u201314 January 2003, Baltimore, Maryland, USA, pp. 444\u2013453. ACM\/SIAM (2003). http:\/\/dl.acm.org\/citation.cfm?id=644108.644179"},{"key":"18_CR33","unstructured":"Kocaoglu, M., Shanmugam, K., Bareinboim, E.: Experimental design for learning causal graphs with latent variables. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017(December), pp. 4\u20139, 2017. Long Beach, CA, USA, pp. 7018\u20137028 (2017), https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/291d43c696d8c3704cdbe0a72ade5f6c-Abstract.html"},{"key":"18_CR34","series-title":"Studies in Mechanobiology, Tissue Engineering and Biomaterials","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-21296-8_3","volume-title":"Uncertainty in Biology","author":"V Lagani","year":"2016","unstructured":"Lagani, V., Triantafillou, S., Ball, G., Tegn\u00e9r, J., Tsamardinos, I.: Probabilistic computational causal discovery for systems biology. In: Geris, L., Gomez-Cabrero, D. (eds.) Uncertainty in Biology. SMTEB, vol. 17, pp. 33\u201373. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-21296-8_3"},{"issue":"12","key":"18_CR35","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0167822","volume":"11","author":"GD Marmerola","year":"2016","unstructured":"Marmerola, G.D., Oikawa, M.A., Dias, Z., Goldenstein, S., Rocha, A.: On the reconstruction of text phylogeny trees: evaluation and analysis of textual relationships. PLoS ONE 11(12), e0167822 (2016)","journal-title":"PLoS ONE"},{"key":"18_CR36","doi-asserted-by":"publisher","unstructured":"Mathieu, C., Zhou, H.: A simple algorithm for graph reconstruction. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, 6\u20138 September 2021, Lisbon, Portugal (Virtual Conference). LIPIcs, vol. 204, pp. 68:1\u201368:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.68","DOI":"10.4230\/LIPIcs.ESA.2021.68"},{"issue":"27","key":"18_CR37","doi-asserted-by":"publisher","first-page":"7361","DOI":"10.1073\/pnas.1510493113","volume":"113","author":"N Meinshausen","year":"2016","unstructured":"Meinshausen, N., Hauser, A., Mooij, J.M., Peters, J., Versteeg, P., B\u00fchlmann, P.: Methods for causal inference from gene perturbation experiments and validation. Proc. Natl. Acad. Sci. 113(27), 7361\u20137368 (2016)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"18_CR38","doi-asserted-by":"crossref","unstructured":"Moffa, G.: Using directed acyclic graphs in epidemiological research in psychosis: an analysis of the role of bullying in psychosis. Schizophr. Bull. 43(6), 1273\u20131279 (2017)","DOI":"10.1093\/schbul\/sbx013"},{"key":"18_CR39","doi-asserted-by":"crossref","unstructured":"Pfeffer, A., et al.: Malware analysis and attribution using genetic information. In: 2012 7th International Conference on Malicious and Unwanted Software, pp. 39\u201345. IEEE (2012)","DOI":"10.1109\/MALWARE.2012.6461006"},{"key":"18_CR40","doi-asserted-by":"publisher","unstructured":"Ranade, A.G.: Optimal speedup for backtrack search on a butterfly network. In: Leighton, T. (ed.) Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA \u201991, Hilton Head, South Carolina, USA, 21\u201324 July 1991, pp. 40\u201348. ACM (1991). https:\/\/doi.org\/10.1145\/113379.113383","DOI":"10.1145\/113379.113383"},{"issue":"3","key":"18_CR41","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2006.08.013","volume":"101","author":"L Reyzin","year":"2007","unstructured":"Reyzin, L., Srivastava, N.: On the longest path algorithm for reconstructing trees from distance matrices. Inf. Process. Lett. 101(3), 98\u2013100 (2007). https:\/\/doi.org\/10.1016\/j.ipl.2006.08.013","journal-title":"Inf. Process. Lett."},{"key":"18_CR42","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.tcs.2021.01.006","volume":"859","author":"G Rong","year":"2021","unstructured":"Rong, G., Li, W., Yang, Y., Wang, J.: Reconstruction and verification of chordal graphs with a distance oracle. Theor. Comput. Sci. 859, 48\u201356 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.01.006","journal-title":"Theor. Comput. Sci."},{"key":"18_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2022.03.008","volume":"917","author":"G Rong","year":"2022","unstructured":"Rong, G., Yang, Y., Li, W., Wang, J.: A divide-and-conquer approach for reconstruction of $$\\{c_{\\ge 5}\\}$$-free graphs via betweenness queries. Theor. Comput. Sci. 917, 1\u201311 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.03.008","journal-title":"Theor. Comput. Sci."},{"key":"18_CR44","doi-asserted-by":"publisher","first-page":"41002","DOI":"10.1109\/ACCESS.2018.2856865","volume":"6","author":"B Shen","year":"2018","unstructured":"Shen, B., Forstall, C.W., de Rezende Rocha, A., Scheirer, W.J.: Practical text phylogeny for real-world settings. IEEE Access 6, 41002\u201341012 (2018). https:\/\/doi.org\/10.1109\/ACCESS.2018.2856865","journal-title":"IEEE Access"},{"key":"18_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/BFb0105127","volume-title":"Conpar 81","author":"Y Shiloach","year":"1981","unstructured":"Shiloach, Y., Vishkin, U.: Finding the maximum, merging and sorting in a parallel computation model. In: Brauer, W., et al. (eds.) CONPAR 1981. LNCS, vol. 111, pp. 314\u2013327. Springer, Heidelberg (1981). https:\/\/doi.org\/10.1007\/BFb0105127"},{"issue":"4","key":"18_CR46","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G Tardos","year":"1989","unstructured":"Tardos, G.: Query complexity, or why is it difficult to seperate NP $${}^{\\text{ a }}$$ cap co np$${}^{\\text{ a }}$$ from p$${}^{\\text{ a }}$$ by random oracles a? Comb. 9(4), 385\u2013392 (1989). https:\/\/doi.org\/10.1007\/BF02125350","journal-title":"Comb."},{"issue":"2","key":"18_CR47","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1093\/ije\/dyaa213","volume":"50","author":"PW Tennant","year":"2021","unstructured":"Tennant, P.W., et al.: Use of directed acyclic graphs (DAGS) to identify confounders in applied health research: review and recommendations. Int. J. Epidemiol. 50(2), 620\u2013632 (2021)","journal-title":"Int. J. Epidemiol."},{"issue":"1","key":"18_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-017-08582-x","volume":"7","author":"S Triantafillou","year":"2017","unstructured":"Triantafillou, S., Lagani, V., Heinze-Deml, C., Schmidt, A., Tegner, J., Tsamardinos, I.: Predicting causal relationships from biological data: applying automated causal discovery on mass cytometry data of human immune cells. Sci. Rep. 7(1), 1\u201311 (2017)","journal-title":"Sci. Rep."},{"issue":"3","key":"18_CR49","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: Parallelism in comparison problems. SIAM J. Comput. 4(3), 348\u2013355 (1975). https:\/\/doi.org\/10.1137\/0204030","journal-title":"SIAM J. Comput."},{"key":"18_CR50","doi-asserted-by":"publisher","unstructured":"Wang, Z., Honorio, J.: Reconstructing a bounded-degree directed tree using path queries. In: 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019, Monticello, IL, USA, 24\u201327 September 2019, pp. 506\u2013513. IEEE (2019). https:\/\/doi.org\/10.1109\/ALLERTON.2019.8919924","DOI":"10.1109\/ALLERTON.2019.8919924"},{"issue":"1","key":"18_CR51","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1006\/jcss.1997.1495","volume":"55","author":"AC Yao","year":"1997","unstructured":"Yao, A.C.: Decision tree complexity and betti numbers. J. Comput. Syst. Sci. 55(1), 36\u201343 (1997). https:\/\/doi.org\/10.1006\/jcss.1997.1495","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2022: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20624-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T23:05:58Z","timestamp":1667084758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guanajuato","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/delta.cs.cinvestav.mx\/~francisco\/Latin22\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"114","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}