commit 0fc6762b6c647c7c9ba0931cb53026006d293953
parent 43c75415d4d0582cd020996757bc6ae2c8fd12b0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 12 Jan 2025 00:46:40 +0100
commit with codex
Diffstat:
20 files changed, 239 insertions(+), 8 deletions(-)
diff --git a/automata_symmetric b/automata_symmetric
@@ -8,3 +8,5 @@ Studied in [kutrib2022finite] in a [deterministic] and [nondeterministic] settin
See also: [automata_reversible], [turing_machine_symmetric]
Up: [automata]
+
+Aliases: symmetric automata
diff --git a/composition b/composition
@@ -0,0 +1,6 @@
+# Composition
+
+- [composition_law]
+- [function_composition]
+
+Up: [mathematics]
diff --git a/connected_component b/connected_component
@@ -0,0 +1,7 @@
+# Connected component
+
+An [equivalence_class] of the [reachability] [equivalence_relation] in an [undirected_graph]
+
+See also: [strongly_connected_component]
+
+Up: [graph_basic_notions]
diff --git a/forest b/forest
@@ -5,3 +5,5 @@ A [set] of [trees] (for [tree_unordered]), or possibly a [sequence] of [trees] (
Generalization: [pseudoforest]
Up: [data_structure]
+
+Aliases: forests
diff --git a/graph b/graph
@@ -0,0 +1,94 @@
+# Graph
+
+[graph_definition]
+
+## Basic notions
+
+See [graph_basic_notions]
+
+## Advanced notions
+
+- [graph_minor]
+ - [robertson_seymour]
+
+## Types
+
+- [graph_undirected] or [graph_directed]
+- [graph_weighted]
+ - [graph_weighted_regimes]: question of how weights are encoded
+ - e.g., [unary] or [binary]
+- [multigraph]
+
+## [Graph_tractability]
+
+- [width_measure]
+- [graph_decomposition]
+
+## [theorems]
+
+- [graph_theorem]
+
+## Results
+
+- [handshaking_lemma], consequence of [degree_sum_formula]
+- [graph_removal_lemma]
+
+## [graph_algorithm]
+
+- [floyd_warshall]
+- [bellman_ford]
+- [dijkstras_algorithm]
+
+## [graph_family]
+
+See [graph_family]
+
+## [graph_problem]
+
+See [graph_problem]
+
+## Fields
+
+- [graph_theory]
+ - [pursuit_evasion]
+ - [extremal_graph_theory]
+
+## Constructions
+
+- [cayley_graph]
+- [line_graph]
+- [dual_graph]
+- [incidence_graph]
+- [graph_complementation]
+
+## [graph_operations]
+
+- [graph_union]
+- [graph_product]
+- [edge_contraction]
+
+## Software
+
+[graph_software]
+
+## Problems
+
+- [minimum_linear_arrangement]
+- [graph_sandwich_problem]
+- [planarity_testing]
+
+## Graph representations
+
+- [adjacency_list]
+- [adjacency_matrix]
+
+## Generalizations
+
+- [hypergraph]
+- [multigraph]
+
+See also: [graph_database], [graph_theory], [graph_query_languages], [game_on_graph]
+
+Up: [data_structure], [computer_science]
+
+Aliases: graphs
diff --git a/graph_modification_treewidth b/graph_modification_treewidth
@@ -0,0 +1,5 @@
+# Graph modification treewidth
+
+- reducing [treewidth] by removing [graph] [edges]: [marchand2022tree]
+
+Up: [treewidth], [graph_modification]
diff --git a/graph_theorem b/graph_theorem
@@ -0,0 +1,7 @@
+# Graph theorem
+
+- [graph_structure_theorem]
+- [four_color_theorem]
+- [strong_perfect_graph_theorem]
+
+Up: [graph]
diff --git a/graph_theory b/graph_theory
@@ -2,5 +2,7 @@
- [friendship_theorem]
- [handshaking_lemma]
+- [pursuit_evasion]
+- [extremal_graph_theory]
Up: [theoretical_computer_science] on [graph]
diff --git a/level_ancestor b/level_ancestor
@@ -0,0 +1,10 @@
+# Level ancestor
+
+Do [preprocessing] on [tree] and compute [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth])
+
+Can be done with linear preprocessing of the tree and constant query time
+- cf for instance [bender2004level]
+- [alstrup2000improved] for [trees] under [updates], and to find the node with minimum weight on the path between two nodes when the tree is weighted
+- [bender2003level]: simplified version of the problem (decompose into [microtrees])
+
+Up: [data_structure]
diff --git a/mathematics b/mathematics
@@ -34,6 +34,7 @@
- [cartesian_product]
- [plane_mathematics]
- [modulo]
+- [relation_mathematics]
## Notions
@@ -50,6 +51,8 @@
- [equality]
- [inequality_mathematics]
- [disequality]
+- [symmetry]
+- [composition]
## Fields
diff --git a/out_tree b/out_tree
@@ -0,0 +1,5 @@
+# Out tree
+
+A [directed_graph] whose underlying [undirected_graph] is a [tree_unrooted] and all [edges] are pointing towards the [leaves]
+
+Up: [tree]
diff --git a/relation_mathematics b/relation_mathematics
@@ -0,0 +1,13 @@
+# Relation (mathematics)
+
+A relation on a set X is a subset of X times X ([cartesian_product])
+
+- [relation_symmetric]
+- [relation_reflexive]
+- [relation_transitive]
+
+Up: [mathematics]
+
+See also: [graph_directed], [composition_law]
+
+Aliases: mathematics relation
diff --git a/strong_connectivity_augmentation b/strong_connectivity_augmentation
@@ -0,0 +1,12 @@
+# Strong connectivity augmentation
+
+https://en.wikipedia.org/wiki/Strong_connectivity_augmentation
+
+minimal number of [edges] to add to make a [directed_graph] [strongly_connected]
+
+- can be solved in [linear_time] in the unweighted setting
+- [NP_complete] in the setting of [weighted_graphs]
+
+cf [raghavan2005note]
+
+Up: [strongly_connected_component], [graph_modification]
diff --git a/strongly_connected_component b/strongly_connected_component
@@ -9,4 +9,4 @@ Up: [graph]
See also: [biconnected_component], [connected_component], [strongly_connected]
-Aliases: SCC
+Aliases: SCC, strongly connected components
diff --git a/transitivity b/transitivity
@@ -4,3 +4,5 @@
- [transitive_closure]
Up: [mathematics]
+
+See also: [relation_transitive]
diff --git a/tree b/tree
@@ -19,6 +19,7 @@
- [tree_binary_full]
- [tree_rooted]
- [tree_unrooted]
+- [tree_balanced]
- [path]
- [downward_path]
@@ -50,6 +51,8 @@
## Related notions and application cases in [TCS]
+- [heap]
+- [binary_search_tree]
- [tree_automaton]
- [range_tree]
- [tree_decomposition]
diff --git a/tree_balancing b/tree_balancing
@@ -0,0 +1,14 @@
+# Tree balancing
+
+Ensure that [tree] is [tree_balanced], and maintain it upon changes to the tree
+
+[Data_structures]:
+
+- [avl_tree]
+- [red_black_tree]
+- [splay_tree]
+- [top_tree]
+
+See also: [avl_tree], [binary_search_tree]
+
+Up: [trees]
diff --git a/tree_decomposition_updating b/tree_decomposition_updating
@@ -0,0 +1,6 @@
+# Updating tree decomposition
+
+- [korhonen2023dynamic]
+- [gottlob2022incremental], sur [generalized_hypertree_decomposition]
+
+Up: [incremental_maintenance] of [tree_decomposition]
diff --git a/treewidth b/treewidth
@@ -0,0 +1,45 @@
+# Treewidth
+
+A [width_measure] on [graphs]
+
+[treewidth_definition]
+
+## Small values
+
+- [Graphs] of treewidth 1 are precisely [forests], including [trees]
+- [treewidth_2]
+
+## Variants
+
+- [hypertreewidth]
+- [submodular_width]
+
+## Related notions
+
+- [grid_minor]
+- [bramble]
+- [contraction] never makes treewidth increase
+
+## Generalizations and related problems
+
+- [tree_decomposition_updating]
+- [semantic_treewidth] for [queries]
+- [graph_modification_treewidth]
+- [treewidth_directed]
+
+## [Computational_problem]
+
+- [Treewidth_computation]
+- [Treewidth_approximation]
+
+## Applications in [TCS]
+
+- [bidimensionality]
+
+## Practical applications
+
+[treewidth_practical]
+
+Up: [width_measure]
+
+See also: [courcelle_theorem], [treelike_data], [message_passing], [pursuit_evasion], [elimination_order], [obstruction]
diff --git a/treewidth_practical b/treewidth_practical
@@ -1,7 +0,0 @@
-# Treewidth practical
-
-- [senellart], [silviu]: [silviu2019experimental]
-- [marx2020four]
-- practical works such as [goharshady2020efficient]
-
-Up: [treewidth]
