Abstract
In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the weights of edges can be modified only within given intervals. We further consider the constrained case in which the total modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover problems. © Springer 2006.
| Original language | English |
|---|---|
| Pages (from-to) | 467-474 |
| Journal | Journal of Global Optimization |
| Volume | 34 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Mar 2006 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
∗This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02).
Research Keywords
- Hamming distance
- Inverse optimization problem
- Minimum spanning tree
RGC Funding Information
- RGC-funded
Fingerprint
Dive into the research topics of 'Constrained inverse minimum spanning tree problems under the bottleneck-type hamming distance'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver