commit d47d04dc69b5b70d520b7d1e4cf281fbc90127f2
parent 35f58ef7ca014ac90cfd2f7ca643fe105776bc13
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 30 Oct 2025 12:10:01 +0100
commit with codex
Diffstat:
16 files changed, 64 insertions(+), 9 deletions(-)
diff --git a/algorithms b/algorithms
@@ -8,6 +8,8 @@ Type:
- [algorithm_combinatorial]
- [algorithm_randomized]
- [greedy_algorithm]
+- [graph_algorithms]
+- [text_algorithms]
By date:
- [algorithms_recent]: a choice of recent algorithms on major [computational_problem]
diff --git a/antichain b/antichain
@@ -3,3 +3,5 @@
In a [poset], an *antichain* is a subset of elements that are pairwise [incomparable]
Up: [partial_order]
+
+See also: [antichain_coverage]
diff --git a/bridge b/bridge
@@ -2,8 +2,10 @@
https://en.wikipedia.org/wiki/Bridge_(graph_theory)
-An [edge] of a graph whose [edge_removal] increases the number of [connected_components] of the [graph]
+An [edge] of a [graph] whose [edge_removal] increases the number of [connected_components] of the [graph]
-See also: [graph_bridgeless], [bridge_set]
+Variant: [strong_bridge] in [directed_graphs]
+
+See also: [graph_bridgeless], [bridge_set], [cut_vertex]
Up: [edge]
diff --git a/connected_component b/connected_component
@@ -2,9 +2,13 @@
An [equivalence_class] of the [reachability] [equivalence_relation] in an [undirected_graph]
+Variants:
+
- [weakly_connected_component]
+- [strongly_connected_component]
+- [biconnected_component]
-See also: [strongly_connected_component], [graph_connected]
+See also: [graph_connected]
Up: [graph_basic_notions]
diff --git a/cut_vertex b/cut_vertex
@@ -0,0 +1,9 @@
+# Cut vertex
+
+A *cut vertex* in a [graph] is a [vertex] whose [vertex_removal] increases the number of [connected_components] of the [graph]
+
+Up: [bridge]
+
+See also: [biconnected_component]
+
+Aliases: cut vertices, articulation point, articulation points
diff --git a/graph_basic_notions b/graph_basic_notions
@@ -3,6 +3,8 @@
- [degree]
- [connected_component]
- [connectivity]
+ - [graph_connected]
+ - [graph_biconnected]
- [strongly_connected]
- [strongly_connected_component]
- [path]
diff --git a/graph_biconnected b/graph_biconnected
@@ -0,0 +1,9 @@
+# Biconnected graph
+
+A *biconnected graph* is an [undirected_graph] which is [connected] and has no [cut_vertex]
+
+Up: [graph_basic_notions]
+
+Aliases: biconnected graph, biconnected graphs
+
+See also: [biconnected_component], [block_cut_tree]
diff --git a/graph_connected b/graph_connected
@@ -2,7 +2,7 @@
A [graph] ([directed_graph] or [undirected_graph]) having only one [connected_component]
-See also: [strongly_connected_graph]
+See also: [strongly_connected_graph], [graph_biconnected]
Up: [graph]
diff --git a/graph_cubic b/graph_cubic
@@ -8,4 +8,4 @@ Up: [maximal_degree]
Aliases: cubic graph, cubic graphs
-See also: [degree_3_graph], [graph_cube]
+See also: [degree_3_graph], [graph_cube], [subcubic_graph]
diff --git a/graph_partition_edges b/graph_partition_edges
@@ -2,8 +2,11 @@
Partitioning the edges of a [graph] into specified patterns
-- [dyer1985complexity] [np_hard] to partition into [connected] [subgraphs] of size 3 even in case of [planar_graphs], and other results
-- [bulteau2016decomposing]: also in the case of [graph_cubic]
+- [dyer1985complexity] [NP_hard] to partition into [connected] [subgraphs] of size 3 even in case of [planar_graphs], and other results
+- [bulteau2016decomposing]: also in the case of [cubic_graphs]
+- Partitioning into [P3] is in [PTIME], it can be done by reduction to [perfect_matching]
+ - Also discussed in [diwan2015p3]
+ - In fact for simple undirected graphs a solution always exist when the connected components have an even number of edges, see [diwan2017decomposing]
Variant: partitioning the vertices, see [graph_partition]
diff --git a/path_graph b/path_graph
@@ -20,3 +20,5 @@ special case:
Up: [graph]
See also: [path]
+
+Aliases: path graphs
diff --git a/strong_bridge b/strong_bridge
@@ -0,0 +1,7 @@
+# Strong bridge
+
+A *strong bridge* is an [edge] in a [directed_graph] whose [edge_removal] increases the number of [strongly_connected_components] of the [graph]
+
+See [cairo2023cut]
+
+Up: [bridge]
diff --git a/strong_orientation b/strong_orientation
@@ -0,0 +1,11 @@
+# Strong orientation
+
+https://en.wikipedia.org/wiki/Strong_orientation
+
+Given an [undirected_graph] G, a *strong orientation* of G is a [graph_orientation] G' of G which is a [strongly_connected_graph]
+
+The corresponding [computational_problem] can be solved in [linear_time], but counting the strong orientations is [sharpP_complete]
+
+Up: [strongly_connected]
+
+See also: [Transitive_orientation]
diff --git a/strongly_connected b/strongly_connected
@@ -6,4 +6,4 @@
Up: [mathematics]
-See also: [connected]
+See also: [connected], [strong_orientation]
diff --git a/vertex_deletion b/vertex_deletion
@@ -3,3 +3,5 @@
Removing a [vertex] from a [graph], and doing [edge_removal] of all [edges] that are [incident] to the removed [vertex]
Up: [graph_modification]
+
+Aliases: vertex removal
diff --git a/word b/word
@@ -25,6 +25,6 @@ Special cases:
Up: [formal_language_theory]
-See also: [update_word], [sequence]
+See also: [update_word], [sequence], [text_algorithms]
Aliases: words, string, strings
