2 papers
cs.DS2008
Computing Minimum Spanning Trees with Uncertainty
Thomas Erlebach, Michael Hoffmann, Danny Krizanc +2
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge of the graph only…
cs.DM2008
Trimming of Graphs, with Application to Point Labeling
Thomas Erlebach, Torben Hagerup, Klaus Jansen +2
For , a vertex-weighted graph of total weight is -trimmable if it contains a vertex-induced subgraph of total weight at least and with no simple path o…