Partial inverse min–max spanning tree problem
| Autor: | Javad Tayyebi, Ali Reza Sepasian |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Control and Optimization Spanning tree Applied Mathematics 0211 other engineering and technologies Inverse 0102 computer and information sciences 02 engineering and technology Inverse problem Minimum spanning tree 01 natural sciences Bottleneck Computer Science Applications Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation Discrete Mathematics and Combinatorics Graph (abstract data type) Time complexity Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 40:1075-1091 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-020-00656-3 |
| Popis: | This paper addresses a partial inverse combinatorial optimization problem, called the partial inverse min–max spanning tree problem. For a given weighted graph G and a forest F of the graph, the problem is to modify weights at minimum cost so that a bottleneck (min–max) spanning tree of G contains the forest. In this paper, the modifications are measured by the weighted Manhattan distance. The main contribution is to present two algorithms to solve the problem in polynomial time. This result is considerable because the partial inverse minimum spanning tree problem, which is closely related to this problem, is proved to be NP-hard in the literature. Since both the algorithms have the same worse-case complexity, some computational experiments are reported to compare their running time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink