Talk:SPF

From Progteam

Jump to: navigation, search

A SPF, in graph theoretic terms is an articulation point in an undirected graph. The Tarjan BCC alggrithm runs in linear time, and will identify all SPFs. The full BCC algorithm, for reasons I do not understand, is not to be found in most textbooks, but I think this stripped-down version may appear in many. In case you are so unfortunate as to have the full algorithm, all you need to is drop the stacking and unstacking of edges, since you are not asked to produce the individual pieces of maximal subgraph that do not have any SPFs (aka the biconnected components). --Siegel 19:58, 24 February 2008 (EST)

This seems fairly straightforward, but nontrivial. Anyone want to pick this up? I'd like to see a solution. Hjfreyer 10:38, 27 December 2007 (EST)

Personal tools