×

Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem. (English) Zbl 0961.90087

Summary: Given an undirected graph and a fixed root node on it, the minimum rooted \(k\)-subtree problem is the problem of finding a minimum-cost connected subtree with exactly \(k\) edges that includes the root node. Applications of this problem appear in several fields. The problem is proved to be NP-hard. Due to the existence of a root node, we are able to derive a greedy procedure that gives a stronger lower-bound to this problem than those in earlier studies. Heuristics are also discussed to obtain an upper bound. Computational results indicate that the proposed lower bounding procedure is effective when \(k\) is small. Especially for grid-type graphs, we observe that the upper and lower bounds frequently coincide with each other.

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993; R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993 · Zbl 1201.90001
[2] Cao, B., Search – hide games on trees, European Journal of Operational Research, 80, 175-183 (1995) · Zbl 0928.91009
[3] Ehrgott, M.; Freitag, J., K-TREE/K-SUBGRAPH: A program package for minimal weighted \(k\)-cardinality trees and subgraph, European Journal of Operational Research, 93, 224-225 (1996) · Zbl 0925.90368
[4] Ehrgott, M.; Hamacher, H. W.; Freitag, J.; Maffioli, F., Heuristics for the \(k\)-cardinality tree and subgraph problems, Asia-Pacific Journal of Operational Research, 14, 87-114 (1997) · Zbl 0906.90167
[5] Fischetti, M.; Hamacher, H. W.; Jørnsten, K.; Maffioli, F., Weighted \(k\)-cardinality trees: Complexity and polyhedral structure, Networks, 24, 11-21 (1994) · Zbl 0809.90124
[6] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, San Francisco, CA, 1978; M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, San Francisco, CA, 1978 · Zbl 0411.68039
[7] Jörnsten, K.; Løkketangen, A., Tabu search for weighted \(k\)-cardinality trees, Asia-Pacific Journal of Operational Research, 14, 9-26 (1997) · Zbl 0909.90265
[8] Yamada, T.; Takahashi, H.; Kataoka, S., A heuristic algorithm for the mini-max spanning forest problem, European Journal of Operational Research, 91, 565-572 (1996) · Zbl 0918.90135
[9] Yamada, T.; Takahashi, H.; Kataoka, S., A branch-and-bound algorithm for the mini-max spanning forest problem, European Journal of Operational Research, 101, 93-103 (1997) · Zbl 0921.90144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.