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);
       }
diff --git a/test/maps_test.cc b/test/maps_test.cc
--- a/test/maps_test.cc
+++ b/test/maps_test.cc
@@ -85,7 +85,7 @@
     checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
     checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();
     ConstMap<A,B> map1;
-    ConstMap<A,B> map2(B());
+    ConstMap<A,B> map2 = B();
     ConstMap<A,B> map3 = map1;
     map1 = constMap<A>(B());
     map1 = constMap<A,B>();
@@ -143,7 +143,7 @@
   {
     checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
     SparseMap<A,B> map1;
-    SparseMap<A,B> map2(B());
+    SparseMap<A,B> map2 = B();
     SparseMap<A,B> map3 = sparseMap<A,B>();
     SparseMap<A,B> map4 = sparseMap<A>(B());