HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there any CS-trees named after flora-trees?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
afterfloraareanynamedtreesthere

Problem

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real world?

In computer science we have red-black trees, B-trees, quadtrees, and so on. In the biological sense of the word tree, we have palm trees, pine trees, redwood trees, etc.

My question: is there a word $w$ such that a $w$ tree could refer to a physical tree in the real world, or a mathematical object?

Solution

Robert Tarjan defines the palm tree in "Depth-first search and linear graph algorithms" (1972):


Let $P$ be a directed graph of two disjoint edge sets, denoted
$v \rightarrow w$ and $v \overset{-}{\rightarrow} w$ respectively. If $P$
satisfies the following properties:



-
The subgraph $T$ containing the edges $v \rightarrow w$ is a
spanning tree of $P$;

-
Each edge not in $T$ connects a vertex with one of its ancestors in
$T$. The edges $v \overset{-}{\rightarrow} w$ are called the fronds of $P$.


e.g.,

He goes on to prove that the directed graph generated by a depth-first search of a connected graph is a palm tree.

In Collective Tree Spanners and Routing in AT-free Related Graphs, Dragan, Yan, and Corneil construct a specific spanning tree that they call a willow-tree.

Context

StackExchange Computer Science Q#26376, answer score: 4

Revisions (0)

No revisions yet.