diff --git a/lemon/kruskal.h b/lemon/kruskal.h
--- a/lemon/kruskal.h
+++ b/lemon/kruskal.h
@@ -212,6 +212,16 @@
       }
     };
 
+    template <typename T>
+    struct RemoveConst {
+      typedef T type;
+    };
+
+    template <typename T>
+    struct RemoveConst<const T> {
+      typedef T type;
+    };
+
     template <typename Graph, typename In, typename Out>
     struct KruskalOutputSelector<Graph, In, Out,
       typename enable_if<SequenceOutputIndicator<Out>, void>::type > 
@@ -219,7 +229,7 @@
       typedef typename In::value_type::second_type Value;
 
       static Value kruskal(const Graph& graph, const In& in, Out& out) {
-        typedef StoreBoolMap<Out> Map;
+        typedef StoreBoolMap<typename RemoveConst<Out>::type> Map;
         Map map(out);
         return _kruskal_bits::kruskal(graph, in, map);
       }