Spanning Forest Algorithms
As a simple example, say we wish to find the maximum spanning forest of a graph. That is, given a graph and a weight for each edge, find a forest containing every vertex and maximizing the total weight of the edges in the tree. This problem arises in some clustering applications. If we look at the definition of the forest matroid above, we see that the maximum spanning forest is simply the independent set with largest total weight — such a set must span the graph, for otherwise we can add edges without creating cycles. But how do we find it?
Read more about this topic: Weighted Matroid
Famous quotes containing the word forest:
“A favorite of outdoor alcoholics, connoisseurs and Fundamentalists, these pills turn water into wine. In 10 minutes the most fetid swamp scum in the forest can become modest red, elusive and light on first taste, yet playful—one might say a trifle impudent—on the afterbite. Saves pack space by eliminating need for bulky corkscrew, decanter and bottles. Store pills on their sides in a cool dark place.”
—Alfred Gingold, U.S. humorist. Items From Our Catalogue, “Wine Pills,” Avon Books (1982)