Directed acyclic graph with ≤1 directed paths between any two nodes
Not to be confused with MultiTree.
The butterfly network, a multitree used in distributed computation, showing in red the undirected tree induced by the subgraph reachable from one of its vertices.
In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset[1]).
In computational complexity theory, multitrees have also been called strongly unambiguous graphs or mangroves; they can be used to model nondeterministic algorithms in which there is at most one computational path connecting any two states.[2]
Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.[3] If a family tree may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree.[4]
^Allender, Eric; Lange, Klaus-Jörn (1996), "StUSPACE(log n) ⊆ DSPACE(log2n/log log n)", Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1178, Springer-Verlag, pp. 193–202, doi:10.1007/BFb0009495.
^Furnas, George W.; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94), pp. 330–336, doi:10.1145/191666.191778, S2CID 18710118.
^McGuffin, Michael J.; Balakrishnan, Ravin (2005), "Interactive visualization of genealogical graphs", IEEE Symposium on Information Visualization, Los Alamitos, California, US: IEEE Computer Society, p. 3, doi:10.1109/INFOVIS.2005.22, S2CID 15449409.
In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most...
of extinct languages List of endangered languages in Europe "Aequian - MultiTree". LINGUIST List. Archived from the original on 9 March 2015. Retrieved...
adding I preserves the property that all matrix coefficients are 0 or 1. A multitree (also called a strongly unambiguous graph or a mangrove) is a DAG in which...
language. It was spoken by Latins who lived close to Rome. "Lanuvian – MultiTree". multitree.org. Retrieved 20 March 2017.[dead link] Sturtevant, E. H. (1920)...
New York: Elsevier. Linguistic maps (from Muturzikin) Ethnologue The Multitree Project Lenguas del mundo (World Languages) Comparative Swadesh list tables...
Retrieved 31 March 2015. Silesian at Ethnologue (25th ed., 2022) "Silesian". MultiTree: A Digital Library of Language Relationships. Archived from the original...
Woolner, Alfred C. "Introduction to Prakrit". Calcutta: University of the Punjab. Retrieved 2 March 2016. "Sauraseni Prakrit - MultiTree".[dead link] v t e...
théorique et appliquée (in French). 10 (1): 215–288. Glottolog Ethnologue MultiTree Project Archived 2016-03-04 at the Wayback Machine Comparative Swadesh...
an inscription of a 3rd-century plate from Bori, Georgia. "Armazic - MultiTree". LINGUIST List. Archived from the original on 12 December 2019. Retrieved...
language category of words in Wiktionary, the free dictionary. Edomite at MultiTree on the Linguist List Lemaire, André (2013). "Edomite and Hebrew". In Khan...
'upper' and ulo 'lower'. Meryans Meryan language Volga Finns "Meshcherian". MultiTree. 2009-06-22. Archived from the original on July 12, 2012. Retrieved 2012-07-13...
Francisco Bay. All of the population has shifted to English. Bay Miwok at MultiTree on the Linguist List Saclan at the Survey of California and Other Indian...
Iranian languages Khwarezm Zoroastrianism Zamakhshari Khwārezmian at MultiTree on the Linguist List Chwarezmischer Wortindex. pp. 686, 711. D. N. Mackenzie...
words written by Fyodor Matyushkin in 1821 have been preserved. Chuvan at MultiTree on the Linguist List Tailleur O. G., Le dialecte tchouvane du youkaghir...
Marij kalykyn ertymgornyzho, #12 (850), 2006, March, the 24th. "Merya". MultiTree. 2009-06-22. Archived from the original on July 19, 2012. Retrieved 2012-07-13...
letters, Aramaic ideograms are often noted by means of capitals. Sogdian at MultiTree on the Linguist List Jacques Gernet (31 May 1996). A History of Chinese...
Indo-European Languages", Sino-Platonic Papers, vol 239. "Ancient Macedonian". MultiTree: A Digital Library of Language Relationships. Archived from the original...
Matyushkin. Wiktionary has definitions related to Omok language. Omok at MultiTree on the Linguist List Nikolaeva, Irina (2008). "Chuvan and Omok Languages...
arborescence. A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree. The reachability...
language dialects that is common among the Lur people. This dialect is included in the Southern Luri category. ethnologue language archives multitree v t e...
discrimination does not apply to dialects, many of which have been inherited from MultiTree or other sources without verification. Sign languages are listed together...
Karamanids Abbreviated as OAT (EAT in Turkish) Old Anatolian Turkish at MultiTree on the Linguist List Ergin, Muharrem, Osmanlıca Dersleri, BOĞAZİÇİ YAYINLARI...
aggregate bandwidth could be improved. Sincoskie referred to this as a multitree bridge. He and Chase Cotton created and refined the algorithms necessary...
Democratic Republic of the Congo, between Mbangala and Yaka. According to Multitree, the spellings are Şinji (Shinji) and Nuŋgo, rather than Yungo as in Maho...
Adaes Fort St. Jean Baptiste State Historic Site San Antonio Adai at MultiTree on the Linguist List Grant, Anthony P. 1995. John Sibley's Adai vocabulary:...
ISBN 978-0-19-879082-2. "Sorothaptic". ISO 639-3. Summer institute of linguistics. "MultiTree entry for Sorothaptic". Coromines, Joan (1976). Els ploms sorotàptics...
of the Southern Luri dialect of the Luri language. It is spoken by Mamasani Lurs. Bakhtiari dialect ethnologue language archives multitree[dead link]...
Global Information