I am experiencing a problem with multithreading using the boost graph library on a dual core Pentium D platform. If I attempt to calculate average path length of a graph, I get at least a 2x slowdown using multiple threads when using johnson_all_pairs_shortest_path. Calculating betweenness is even worse (~7x) when I use brandes_betweenness_centrality and relative_betweenness_centrality. In my test setup, I have no locks anywhere and no shared memory (the graphs are loaded from a file for each iteration in the test). The graph has been defined similar to the following (I can't get actual code on the list due to restrictions from employer): struct VertexProperties { string name; string group; vector<string> properties; }; struct EdgeProperties { string name; double weight; }; typedef boost::property<...> GraphProperty //a group of enums mapped to doubles and ints typedef boost::adjacency_list<listS, vecS, undirectedS, VertexProperties, EdgeProperties, GraphProperty> BoostGraph; All I have to do in my code to see the slowdown is to use a populated graph with johnson_all_pairs_shortest_path in some iterative loop in both one and multiple threads. A real kicker is that currently I can get around this problem by spawning multiple processes to deal with the data load (so I have an interim solution at least) and that gives me a performance improvement by 2x which I expect with dual core... However, I really want to know why this isn't working in a multi-threaded environment. What could I be doing wrong? Is there some proprocessor #define that makes the boost graph library more thread independent? Is there something wrong with the way that I am declaring the graph? Any help is appreciated! Thanks, Thranil