commit 43c75415d4d0582cd020996757bc6ae2c8fd12b0
parent e47158fd7edb1be3dc77243197e70e84270a586c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 12 Jan 2025 00:15:34 +0100
commit with codex
Diffstat:
17 files changed, 195 insertions(+), 22 deletions(-)
diff --git a/3_dimensional_matching_hardness_proof b/3_dimensional_matching_hardness_proof
@@ -1,11 +0,0 @@
-# 3 dimensional matching hardness proof
-
-Shown NP-hard [nptime] in [garey_johnson], reduction from [3sat]:
-- for each variable do a "flower" gadget
- - http://courses.csail.mit.edu/6.890/fall14/6046-L16.pdf
- - at the center put elements of X and Y that are local to each variable, alternatively
- - at the extremities put elements of Z that correspond either to x or barx
- - for each clause there are two elements of X and Y local to that clause to impose that it is covered, and there are 3 ways to cover that use each "allowed" literal
- - some additional things: for every excess variable occurrences, a gadget with two specific elements of X and Y and all possible Z to cover exactly one unused variable
-
-Up: [3_dimensional_matching]
diff --git a/ancestor b/ancestor
@@ -0,0 +1,7 @@
+# Ancestor
+
+In a [tree], an ancestor of a [node] is a node on the [path] from the [root] to that [node]
+
+Up: [tree]
+
+Aliases: ancestors
diff --git a/child b/child
@@ -0,0 +1,9 @@
+# Child
+
+In a [tree], each node has a sequence of children (for [tree_ordered]) or a set of children. In [tree_binary] there are at most two children
+
+Up: [tree]
+
+Aliases: children
+
+See also: [parent]
diff --git a/data_structure b/data_structure
@@ -16,3 +16,5 @@
See also: [sketching], [algorithms]
Up: [computer_science]
+
+Aliases: data structures
diff --git a/depth b/depth
@@ -1,13 +1,6 @@
# Depth
-The depth of a [circuit] is the maximal [length] of a [path] from a [variable_gate] to the [output_gate] of the [circuit]
+- [depth_circuit]
+- [depth_tree]
-- depth [lower_bounds] on [circuit]:
- - historical work: [hastad1998shinkage]
- - recent work: [bathie2024towards]
-
-- [depth_reduction]
-
-Up: [circuit]
-
-See also: [circuit_size], [height]
+Up: [parameter]
diff --git a/depth_circuit b/depth_circuit
@@ -0,0 +1,13 @@
+# Depth circuit
+
+The depth of a [circuit] is the maximal [length] of a [path] from a [variable_gate] to the [output_gate] of the [circuit]
+
+- depth [lower_bounds] on [circuit]:
+ - historical work: [hastad1998shinkage]
+ - recent work: [bathie2024towards]
+
+- [depth_reduction]
+
+See also: [circuit_size], [height]
+
+Up: [depth], [circuit]
diff --git a/depth_tree b/depth_tree
@@ -0,0 +1,5 @@
+# Depth tree
+
+The depth of a [node] in a [tree] is the length of the [downward_path] from the [root] to that node (so 0 for the [root])
+
+Up: [depth], [tree]
diff --git a/forest b/forest
@@ -0,0 +1,7 @@
+# Forest
+
+A [set] of [trees] (for [tree_unordered]), or possibly a [sequence] of [trees] (for [tree_unordered])
+
+Generalization: [pseudoforest]
+
+Up: [data_structure]
diff --git a/generalized_core_spanner b/generalized_core_spanner
@@ -4,4 +4,4 @@ closure of [spanner_core] under [complementation]
expressive power [thompson2023generalized]
-Up: [spanner]
+Up: [spanner], [generalization]
diff --git a/graph_factorable b/graph_factorable
@@ -0,0 +1,5 @@
+# Graph factorable
+
+- [graph_factorization]
+
+Up: [graph_family]
diff --git a/graph_family b/graph_family
@@ -0,0 +1,46 @@
+# Graph family
+
+A (generally [infinite]) set of [graphs]
+
+- [cycle]
+ - [triangle]
+ - [hole]
+- [path]
+- [tree]
+ - [polytree]
+ - [multitree]
+ - [forest]
+- [bipartite_graph]
+- [interval_graph]
+- [graph_regular]
+ - [graph_cubic]
+- [grid_graph]
+ - [wall_graph]
+- [strongly_connected_graph]
+- [graph_series_parallel]
+
+- [chordal]
+- [planar_graph]
+- [graph_perfect]
+
+- [graph_free]
+ - [graph_h_free]
+ - [graph_induced_h_free]
+ - [graph_pk_free]
+ - [graph_h_minor_free]
+
+- [graph_sparse]
+
+- [cograph]
+- [erdos_renyi_graph]
+- [graph_factorable]
+- [friendship_graph]
+- [berge_graph]
+
+May have the property of being [graph_class_hereditary]
+
+Up: [graph]
+
+Aliases: graph class
+
+See also: [halls_theorem], [network_reliability], [robertson_seymour], [graph_radius_diameter], [turan_theorem], [graph_substructure], [graph_labeling], [erdos_posa], [graph_traversal]
diff --git a/height b/height
@@ -0,0 +1,7 @@
+# Height
+
+A [tree] consisting of only a singleton [root] node has height 0; otherwise the height is 1 plus the [maximum] of the [height] of the [rooted_subtrees] that are [children] of the [root]
+
+Up: [parameter] on [tree]
+
+See also: [depth]
diff --git a/internal_node b/internal_node
@@ -0,0 +1,5 @@
+# Internal node
+
+A [node] in a [tree] which is not a [leaf]
+
+Up: [tree]
diff --git a/node b/node
@@ -0,0 +1,5 @@
+# Node
+
+A [vertex], in a [tree]
+
+Up: [tree]
diff --git a/theoretical_computer_science b/theoretical_computer_science
@@ -46,3 +46,5 @@
- [euclidean_algorithm] for [greatest_common_divisor]
Up: [formal_science], [research_fundamental] of [computer_science]
+
+Aliases: TCS
diff --git a/tree b/tree
@@ -0,0 +1,73 @@
+# Tree
+
+## Basic concepts
+
+- [node]
+- [leaf]
+- [internal_node]
+- [ancestor]
+- [root]
+- [forest]
+- [parent]
+- [child]
+- [height]
+- [tree_unranked]
+- [tree_ranked]
+- [tree_ordered]
+- [tree_binary]
+- [tree_complete]
+- [tree_binary_full]
+- [tree_rooted]
+- [tree_unrooted]
+- [path]
+- [downward_path]
+
+## [Algorithms] on [trees]
+
+- [tree_traversal]
+- [prefix_order], [postfix_order], [infix_order]
+
+## Advanced concepts
+
+- [strahler_number]
+
+## Special cases
+
+- [tree_even] and [tree_odd]
+- [graceful_tree]
+
+## Applications to other fields
+
+- [tree_applications]
+- [xml], [xpath]
+
+## [Data_structures]
+
+- [tree_balancing]
+ - [splay_tree]
+ - [top_tree]
+- [level_ancestor]
+
+## Related notions and application cases in [TCS]
+
+- [tree_automaton]
+- [range_tree]
+- [tree_decomposition]
+- [universal_tree]
+
+## Decomposition of trees
+
+- [centroid_decomposition]
+- [heavy_light_path_decomposition]
+
+## [Generalizations]
+
+- [polytree]
+- [multitree]
+- [out_tree] as a [directed_graph]
+
+Up: [data_structure]
+
+See also: [treewidth], [forest]
+
+Aliases: trees
diff --git a/tree_unrooted b/tree_unrooted
@@ -0,0 +1,5 @@
+# Tree unrooted
+
+A [tree] without a choice of [root], so that it is just a [graph_connected] [undirected_graph] with no [cycles]
+
+Up: [tree]
