diff --git a/test/Makefile.am b/test/Makefile.am
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -1,3 +1,7 @@
+if USE_VALGRIND
+TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
+endif
+
 EXTRA_DIST += \
 	test/CMakeLists.txt
 
@@ -7,6 +11,7 @@
 
 check_PROGRAMS += \
 	test/adaptors_test \
+	test/bellman_ford_test \
 	test/bfs_test \
 	test/circulation_test \
 	test/connectivity_test \
@@ -18,6 +23,7 @@
 	test/edge_set_test \
 	test/error_test \
 	test/euler_test \
+	test/fractional_matching_test \
 	test/gomory_hu_test \
 	test/graph_copy_test \
 	test/graph_test \
@@ -30,7 +36,9 @@
 	test/matching_test \
 	test/min_cost_arborescence_test \
 	test/min_cost_flow_test \
+	test/min_mean_cycle_test \
 	test/path_test \
+	test/planarity_test \
 	test/preflow_test \
 	test/radix_sort_test \
 	test/random_test \
@@ -53,6 +61,7 @@
 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 
 test_adaptors_test_SOURCES = test/adaptors_test.cc
+test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
 test_bfs_test_SOURCES = test/bfs_test.cc
 test_circulation_test_SOURCES = test/circulation_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
@@ -64,6 +73,7 @@
 test_edge_set_test_SOURCES = test/edge_set_test.cc
 test_error_test_SOURCES = test/error_test.cc
 test_euler_test_SOURCES = test/euler_test.cc
+test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
 test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
@@ -78,7 +88,9 @@
 test_matching_test_SOURCES = test/matching_test.cc
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 test_path_test_SOURCES = test/path_test.cc
+test_planarity_test_SOURCES = test/planarity_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc
 test_radix_sort_test_SOURCES = test/radix_sort_test.cc
 test_suurballe_test_SOURCES = test/suurballe_test.cc