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 \
@@ -29,7 +34,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 \
@@ -52,6 +59,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
@@ -76,7 +84,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