Node-Optimal Connected k-Subgraphs
Abstract
In this paper we consider the problem of optimally selecting
a set of k nodes in a node-weighted graph, under the requirement
that the subgraph induced by the set of nodes selected is connected.
This problem arises in a Norwegian off-shore oil-drilling application.
We show this problem to be NP-complete on general graphs, but
provide a polynomial time algorithm to find an optimal solution
for trees. We conclude with some approximation algorithms
for the problem on general graphs.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Node-Optimal Connected k-Subgraphs (6 pages, 91 KB)
,
- Dorit S. Hochbaum and Anu Pathria. Manuscript, August (1994).
dorit@hochbaum.ieor.berkeley.edu
7/30/98