commit 49182d31257b760eed4dd522b87c64a09c5e9364
parent 332d7878aef1e9fc40133d97b38ed2f3ea8cc875
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 22 Sep 2025 14:54:00 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
8 files changed, 54 insertions(+), 12 deletions(-)
diff --git a/automata_parikh b/automata_parikh
@@ -4,8 +4,10 @@ https://fr.wikipedia.org/wiki/Automate_de_Parikh
introduced in [klaedtke2003monadic]
+Also called Z-VASS in [czerwinski2020approach], or integer VASS in [clemente2016separability]
+
Up: [automata_types]
See also: [parikh_image]
-Aliases: Parikh automata
+Aliases: Parikh automata, Parikh automaton
diff --git a/circle_packing_theorem b/circle_packing_theorem
@@ -0,0 +1,9 @@
+# Circle packing theorem
+
+https://en.m.wikipedia.org/wiki/Circle_packing_theorem
+
+Every [undirected_graph] which is [connected_graph] and [planar_graph] can be achieved as an intersection graph of a [circle_packing]
+
+Up: [theorem], [packing_problem]
+
+See also: [intersection_graph], [string_graph]
diff --git a/hamiltonian_cycle b/hamiltonian_cycle
@@ -1,15 +1,7 @@
# Hamiltonian cycle
-[np_hard]
+[Computational_problem]: [Hamiltonian_cycle_problem]
-[approximation] algorithm: [christofides_heuristic]
-
-- [hamiltonian_cycle_cube] on [graph_cube]
-- [hamiltonian_cycle_square] on [graph_square]
-- [hamiltonian_cycle_multiple] going multiple times over each [vertex]
-
-Special case: [Knight's_tour]
-
-Up: [problem] on [graph]
+Up: [cycle]
See also: [graph_eulerian], [hamiltonian_path]
diff --git a/hamiltonian_cycle_problem b/hamiltonian_cycle_problem
@@ -0,0 +1,17 @@
+# Hamiltonian cycle problem
+
+The [decision_problem] of whether an input [undirected_graph] admits a [Hamiltonian_cycle], or the [function_problem] of finding one
+
+It is [NP_hard], like the [Hamiltonian_path_problem]
+
+[Approximation] algorithm: [christofides_heuristic]
+
+- [hamiltonian_cycle_cube] on [graph_cube]
+- [hamiltonian_cycle_square] on [graph_square]
+- [hamiltonian_cycle_multiple] going multiple times over each [vertex]
+
+Special case: [Knight's_tour]
+
+Up: [computational_problem], [hamiltonian_cycle]
+
+See also: [Hamiltonian_path_problem]
diff --git a/hamiltonian_path b/hamiltonian_path
@@ -2,7 +2,7 @@
A [simple_path] that goes via all vertices of a [graph]
-The [computational_problem] of [deciding] whether such a path exists in an input [undirected_graph] is [np_complete]
+[Computational_problem]: [Hamiltonian_path_problem]
See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path]
diff --git a/hamiltonian_path_problem b/hamiltonian_path_problem
@@ -0,0 +1,10 @@
+# Hamiltonian path problem
+
+The [computational_problem] of [deciding] whether an input [undirected_graph] has a [hamiltonian_path]
+
+It is [np_complete], but it is [FPT] [parameterized] by [treewidth]:
+- https://cs.stackexchange.com/questions/59325/an-fpt-algorithm-for-hamiltonian-cycle-running-parameterized-by-treewidth
+
+Up: [decision_problem], [hamiltonian_path]
+
+See also: [Hamiltonian_cycle_problem]
diff --git a/packing_problem b/packing_problem
@@ -9,6 +9,7 @@
- similar looking problem "Heilbronn triangle problem" https://en.wikipedia.org/wiki/Heilbronn_triangle_problem https://www.quantamagazine.org/the-biggest-smallest-triangle-just-got-smaller-20230908/
- conjecture that you can pack any set of [tree] into [clique]: Gyárfás tree packing conjecture
- [ringels_conjecture]
+- [circle_packing_theorem]
Up: [computational_geometry]
diff --git a/string_graph b/string_graph
@@ -0,0 +1,11 @@
+# String graph
+
+https://en.m.wikipedia.org/wiki/String_graph
+
+An [intersection_graph] of curves in the plane
+
+The [decision_problem] of whether an input [undirected_graph] is of this form is [NP_complete] and the [NP] upper bound is nontrivial
+
+Up: [graph_family]
+
+See also: [circle_packing_theorem]
