Abstract | ||
---|---|---|
The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a structured class of greedy heuristics for this NP-hard problem, and identify the best heuristic. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.dam.2005.06.006 | Discrete Applied Mathematics |
Keywords | Field | DocType |
tree partitioning,minimum spanning forests,forest problem,constrained forest problem,greedy heuristics,best heuristic,specified number,tree span,undirected edge-weighted graph,structured class,np-hard problem,greedy heuristic,np hard problem | Discrete mathematics,Graph,Heuristic,Combinatorics,Tree (graph theory),Minimum degree spanning tree,Vertex (geometry),Spanning forest,Heuristics,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
154 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
4 | 0.45 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Laszlo | 1 | 214 | 10.76 |
Sumitra Mukherjee | 2 | 311 | 31.75 |