commit 19e5671c3a592a9c07420bd1df4954a3125b106a
parent 400d079b4b646cdf81bd414f4c315a8402077c9d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 14 Dec 2025 13:41:44 +0100
Merge remote-tracking branch 'origin/master'
Diffstat:
18 files changed, 59 insertions(+), 15 deletions(-)
diff --git a/automaton_upwards_closed b/automaton_upwards_closed
@@ -16,4 +16,4 @@ Up: [language_upwards_closed]
Aliases: upwards closed automaton, Upwards closed automata, automaton subword closed, subword closed automaton, subword closed automata, supersequence closed automaton, supersequence closed automata, automata supersequence closed, automaton supersequence closed
-See also: [downwards_closed_automaton]
+See also: [downwards_closed_automaton], [automaton_subsequence_closed]
diff --git a/chordal b/chordal
@@ -7,7 +7,7 @@ An [undirected_graph] is *chordal* if every [cycle] of length at least 4 has a [
Equivalently, an [undirected_graph] is chordal iff it has a [perfect_elimination_ordering]:
- can be found in [linear_time] with [lexicographic_breadth_first_search]
-See also: [hypergraph_chordal], [proper_chordal_graph]
+See also: [hypergraph_chordal], [proper_chordal_graph], [chordless_path], [chordless_cycle]
Up: [graph]
diff --git a/degree b/degree
@@ -6,7 +6,8 @@ In [directed_graphs], we can distinguish the [indegree] and [outdegree], respect
- [maximal_degree]
- [average_degree]
+- [bounded_degree_structures]
Up: [graph_basic_notions]
-See also: [bounded_degree_graphs]
+See also: [bounded_degree_graphs], [k_regular_graph]
diff --git a/dynamic_membership_push_pop b/dynamic_membership_push_pop
@@ -1,5 +1,8 @@
# Dynamic membership push pop
- for [regular_languages]: [guardian_algorithm] in [ganardi2022low]
+- questions plus générales, genre avec [infix_testing] :
+ - présentation [tudastic]
+ - ce mail: <20200429101934.gu6xz5ok6dljjc3k@mu.a3nm.net>
Up: [dynamic_membership_word], [push_pop]
diff --git a/foucaud2025polynomial b/foucaud2025polynomial
@@ -0,0 +1,7 @@
+# foucaud2025polynomial
+
+Studies [path_cover] and [path_partition] on [trees] and [bounded_treewidth_graphs]; for covering the [vertices]
+
+Also studies the variants requiring pairwise edge-disjointness (like [trails]) and the version with [induced_paths]
+
+Up: [academic_paper] on [path_cover]
diff --git a/graph_packing b/graph_packing
@@ -14,4 +14,4 @@ Can be with [induced_subgraphs] (a "strict factor")
Up: [computational_problem] on [graph]
-See also: [packing_problem], [graph_partition]
+See also: [packing_problem], [graph_partition], [path_cover], [path_partition]
diff --git a/graph_regular b/graph_regular
@@ -1,4 +1,4 @@
-# Graph regular
+# Regular graph
A [graph] where all [vertices] have the same [degree]
@@ -13,4 +13,4 @@ See also: [graph_matching_covered]
Up: [graph]
-Aliases: regular graph
+Aliases: regular graph, k regular graph
diff --git a/incremental_maintenance_datalog b/incremental_maintenance_datalog
@@ -1,5 +1,8 @@
# Incremental maintenance datalog
- [xu2023zodiacedge]
+- [zhao2025flowlog]
Up: [incremental_maintenance], [datalog]
+
+Aliases: datalog incremental
diff --git a/induced_path b/induced_path
@@ -0,0 +1,9 @@
+# Induced path
+
+An [path] as an [induced_subgraph] of another [graph]
+
+Up: [induced_subgraph], [path]
+
+Aliases: chordless path, path induced, paths induced, induced paths, chordless paths
+
+See also: [chordless_cycle]
diff --git a/induced_subgraph b/induced_subgraph
@@ -4,7 +4,7 @@ A [subgraph] of a [graph] defined by taking a [subset] U of [vertices] and takin
- [induced_subgraph_isomorphism]
-See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle], [induced_subinstance]
+See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle], [induced_subinstance], [induced_path]
Up: [graph]
diff --git a/obdd b/obdd
@@ -8,6 +8,8 @@ A [deterministic] [bdd] with a [variable_order]
We can tractably take the [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same
- [OBDD_conjunction]
+Generalization: [CFLOBDDs]
+
Up: [bdd]
See also: [fbdd]
diff --git a/path_cover b/path_cover
@@ -0,0 +1,11 @@
+# Path cover
+
+Given an [undirected_graph] G, compute a minimum-cardinality *path cover*, i.e., a set of paths covering the [vertices] of G (not necessarily pairwise disjoint)
+
+Studied in [foucaud2025polynomial]
+
+[NP_hard] because it generalizes the [Hamiltonian_path_problem]
+
+See also: [graph_packing], [path_partition]
+
+Up: [computational_problem]
diff --git a/path_partition b/path_partition
@@ -0,0 +1,9 @@
+# Path partition
+
+Given an [undirected_graph] G, compute a minimum-cardinality *path partition*, i.e., a set of pairwise disjoint paths covering the [vertices] of G
+
+Mentioned in [foucaud2025polynomial]
+
+[NP_hard] because it generalizes the [Hamiltonian_path_problem]
+
+See also: [path_cover], [graph_packing]
diff --git a/property_testing_csp b/property_testing_csp
@@ -1,5 +0,0 @@
-# Property testing CSP
-
-cf [fei2025unbounded]
-
-Up: [property_testing], [CSP]
diff --git a/subsequence_automaton b/subsequence_automaton
@@ -6,4 +6,6 @@ A *subsequence [automaton]* for a [word] w is an [automaton] A that accepts prec
Up: [subsequence]
-See also: [common_subsequence_automaton], [downwards_closure]
+See also: [common_subsequence_automaton], [downwards_closure], [supersequence_automaton], [automaton_subsequence_closed]
+
+Aliases: automaton subsequence
diff --git a/supersequence b/supersequence
@@ -2,7 +2,7 @@
A [word] u is a *supersequence* of a [word] v if v is a [subsequence] of u
-See also: [subsequence], [supersequence_closure], [automaton_supersequence_closed]
+See also: [subsequence], [supersequence_closure], [automaton_supersequence_closed], [supersequence_automaton]
Up: [formal_language_theory], [stringology]
diff --git a/treelike_data b/treelike_data
@@ -5,3 +5,5 @@ Data which is [treelike], i.e., of bounded [treewidth]
On such data we can do [pqe_mso]
Up: [data] of bounded [treewidth], [types_of_data]
+
+See also: [bounded_treewidth_graph]
diff --git a/word b/word
@@ -25,6 +25,6 @@ Special cases:
Up: [formal_language_theory]
-See also: [update_word], [sequence], [text_algorithms]
+See also: [update_word], [sequence], [text_algorithms], [endmarker]
Aliases: words, string, strings
