I've also noticed that when in/out edge lists are stored in an associative container and the parallel edges are allowed, i.e multiset is used, the functions remove_edge()/clear_vertex() do not work as efficient as they could. The calls to these functions (in my case) result in the following sequence of calls: // O(E/V) template <class EdgeList, class vertex_descriptor> void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, allow_parallel_edge_tag) { boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v)); } Then: template <class Container, class Predicate> void erase_if(Container& c, Predicate p) { erase_if_dispatch(c, p, container_category(c), iterator_stability(c)); } Then: template <class AssociativeContainer, class Predicate> void erase_if_dispatch(AssociativeContainer& c, Predicate p, associative_container_tag, stable_tag) { typename AssociativeContainer::iterator i, next; for (i = next = c.begin(); next != c.end(); i = next) { ++next; if (p(*i)) c.erase(i); } } The complexity of the search operation is linear, so multiset doesn't provide a performance advantage over containers such as vector or set. However, the function erase_if_dispatch() could use multiset's equal_range() member function, which would result in O(log n) complexity of the search. I understand that the reason erase_if_dispatch() is written in the way it is written, is probably that the function is generic with regard to the predicate and doesn't do assumptions on it. However, in the case erase_if_dispatch() is called from erase_from_incidence_list(), where the predicate is set, the function (its special specialization) could make assumption that the predicate is actually the same as the predicate used to sort the in/out edge list itself (the target vertex), and therefore could use equal_range() to boost the performance of the function. --Yulik.