wiki_research

commit 7974de3bf9056966bc5b2ac6739be37ba81dd10c
parent 9f3282ec76f516d6589b6af0e54b951680e307b3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 31 Dec 2024 00:01:18 +0100

commit with codex

Diffstat:
adjacency_matrix
 | 
14
++++++++++++++
antihole
 | 
5
+++++
even_hole_free_graph
 | 
12
++++++++----
graph_algorithm
 | 
2
++
graph_complementation
 | 
2
++
graph_representation
 | 
10
++++++++++
graph_weighted
 | 
6
++++--

7 files changed, 45 insertions(+), 6 deletions(-)
diff --git a/adjacency_matrix b/adjacency_matrix
@@ -0,0 +1,14 @@
+# Adjacency matrix
+
+A [matrix] indicating which [edges] exist in a [graph]
+
+- can be [Boolean_matrix] to indicate the existence of edges
+- can store [edge] weights / distances
+
+May be [sparse_matrices] for [sparse_graphs]
+
+Up: [graph_representation]
+
+Aliases: adjacency matrices
+
+See also: [adjacency_list]
diff --git a/antihole b/antihole
@@ -0,0 +1,5 @@
+# Antihole
+
+[Graph_complement] of a [hole]
+
+Up: [hole]
diff --git a/even_hole_free_graph b/even_hole_free_graph
@@ -1,9 +1,13 @@
-# Even hole free graph
+# Even-hole-free graph
 
-[graph_undirected] without [hole] of even length
+https://en.wikipedia.org/wiki/Even-hole-free_graph
+
+A [graph_undirected] without [hole] of [even] length
 
 [survey_paper]: [vuskovic2010even]
 
-Up: [undirected_graph], [hole]
+It is an [open_problem] whether [graph_coloring] or [maximum_independent_set] computation is [PTIME] on even-hole-free graphs
+
+Up: [undirected_graph], [hole], [graph_tractability]
 
-See also: [graph_perfect]
+See also: [graph_perfect], [even_cycle_free_graph]
diff --git a/graph_algorithm b/graph_algorithm
@@ -15,3 +15,5 @@
 - [transitive_orientation]
 
 Up: [algorithms] on [graph]
+
+Aliases: graph algorithms
diff --git a/graph_complementation b/graph_complementation
@@ -3,3 +3,5 @@
 [Undirected_graph] formed from an other graph G by keeping the same set of [vertices] and taking precisely the [edges] that are not in G
 
 Up: [graph], [complementation]
+
+Aliases: graph complement
diff --git a/graph_representation b/graph_representation
@@ -0,0 +1,10 @@
+# Graph representation
+
+Ways to represent a [graph] in [memory]:
+
+- [adjacency_matrix]
+- [adjacency_list]
+- [sorted_list] of edges
+- [graph_compressed_representation]
+
+Up: [graph_basic_notions]
diff --git a/graph_weighted b/graph_weighted
@@ -1,8 +1,10 @@
 # Graph weighted
 
-graph where [edge]s carry [weight]
+A [graph] where [edges] carry [weight]
 
-can be used for [shortest_path]
+[Graph_algorithms] to typically run on such graphs:
+- [shortest_path]
+- [minimum_spanning_tree]
 
 [graph_weighted_regimes]