commit ae8d9586d5a40be2f7d7dd807e15db5f9ded48a8
parent 69ad15638a794fdf4be98f94fbf4a5f6265aeaf6
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 1 Jun 2025 19:32:02 +0200
commit with codex
Diffstat:
15 files changed, 51 insertions(+), 8 deletions(-)
diff --git a/algorithms_list b/algorithms_list
@@ -1,5 +1,7 @@
# Algorithms list
+- [algorithm_type]
+
- On [graph]: [graph_algorithm]
- [sampling]
- [batch_partial_match]
@@ -16,6 +18,4 @@
- [stable_marriage]
- [binary_search]
-- [algorithm_type]
-
Up: [algorithms]
diff --git a/automata_deterministic b/automata_deterministic
@@ -6,3 +6,5 @@
Up: [automata_types], [determinism_language]
Aliases: automaton deterministic, deterministic automaton, deterministic automata, DFA, DFAs, automaton determinism, automata determinism
+
+See also: [determinization]
diff --git a/automata_determinization b/automata_determinization
@@ -13,4 +13,4 @@ Bounds for specific [automata_classes]:
Up: [automata_constructions]
-Aliases: automata determinized
+Aliases: automata determinized, determinization
diff --git a/automata_two_way b/automata_two_way
@@ -2,7 +2,7 @@
[Automata] that can read the input [word] in both directions
-It is an [open_problem] if two-way automata can be [automata_determinized] in [PTIME]. This is related to open problems in [complexity_theory], cf [kapoutsis2013two]: [sakoda_sipser_conjecture]
+[Automata_two_way_determinization]
Can be converted back to [automata_one_way].
- Elementary construction to get an [automata_nondeterministic] for the complement language in [vardi1989note] with exp(n) blowup
diff --git a/automata_two_way_determinization b/automata_two_way_determinization
@@ -0,0 +1,8 @@
+# Automata two way determinization
+
+It is an [open_problem] if [two_way_automata] can be [automata_determinized] in [PTIME].
+- This is related to open problems in [complexity_theory]
+ - cf [kapoutsis2013two]: [sakoda_sipser_conjecture]
+- cf [hromkovic2003nondeterminism]
+
+Up: [automata_two_way], [determinization]
diff --git a/context_free_grammar b/context_free_grammar
@@ -41,7 +41,7 @@
- [probabilistic_grammar]
-See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series]
+See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar]
Up: [formal_language_theory]
diff --git a/determinism b/determinism
@@ -4,3 +4,5 @@
- [deterministic] (for [circuit])
Up: [theoretical_computer_science]
+
+See also: [determinization]
diff --git a/graph_algorithm b/graph_algorithm
@@ -1,6 +1,7 @@
# Graph algorithm
-- [network_flow]
+- [network_flow]: [flow_algorithm]
+ - [edmonds_karp_algorithm]
- [maximum_matching] for [matching]
- [maximum_weighted_matching] and [hungarian_algorithm]
- [shortest_path] ([graph_distance])
diff --git a/graph_coloring b/graph_coloring
@@ -21,7 +21,8 @@
- [edge_coloring]
- [list_coloring]
- [graph_coloring_counting]
-- [H_coloring]:
+- [H_coloring]
+- [Grundy_number]
## Complexity
diff --git a/grundy_number b/grundy_number
@@ -0,0 +1,9 @@
+# Grundy number
+
+The *Grundy number* of an [undirected_graph] is the highest number of colors that are used when coloring [vertices] using a [greedy_algorithm], across all possible orders in which vertices can be considered
+
+A [graph] is [graph_well_colored] if its [chromatic_number] is equal to its [Grundy_number]
+
+Up: [graph_coloring]
+
+See also: [chromatic_number]
diff --git a/hyperedge b/hyperedge
@@ -5,3 +5,5 @@ A set of [vertices] in a [hypergraph]
Up: [hypergraph], [edge]
Aliases: hyperedges
+
+See also: [Hyperedge_replacement_grammar]
diff --git a/hyperedge_replacement_grammar b/hyperedge_replacement_grammar
@@ -0,0 +1,7 @@
+# Hyperedge replacement grammar
+
+[chiang2013parsing]
+
+Up: [grammar], [hypergraph]
+
+Aliases: Hyperedge replacement grammars
diff --git a/hypergraph b/hypergraph
@@ -27,7 +27,7 @@ generalizes [graph]
- [hyperclique_detection] / [hyperclique_hypothesis]
-See also: [generalized_hypertree_width], [conjunctive_query], [relational_instance], [simplicial_complex]
+See also: [generalized_hypertree_width], [conjunctive_query], [relational_instance], [simplicial_complex], [Hyperedge_replacement_grammar]
Up: [data_structure], [computer_science]
diff --git a/minimum_cost_flow b/minimum_cost_flow
@@ -0,0 +1,9 @@
+# Minimum cost flow
+
+https://en.wikipedia.org/wiki/Minimum-cost_flow_problem
+
+You want to send a certain amount of flow through a [flow_network], but edges have costs and you want to minimize the cost
+
+Solvable in [PTIME] by [linear_programming]
+
+Up: [network_flow]
diff --git a/partial_order b/partial_order
@@ -26,3 +26,5 @@ Variants:
Up: [mathematics], [order]
See also: [preorder], [monotone]
+
+Aliases: poset, posets, partial orders
