patternMinor
Are there any CS-trees named after flora-trees?
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?
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.
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.