Details of Research Outputs

TitleSwap-vertex based neighborhood for Steiner tree problems
Author (Name in English or Pinyin)
Fu, Zhang-Hua1,2; Hao, Jin-Kao2,3
Date Issued2017-06-01
Source PublicationMATHEMATICAL PROGRAMMING COMPUTATION
ISSN1867-2949
DOI10.1007/s12532-016-0116-8
Indexed ByEI
Firstlevel Discipline计算机科学技术
Education discipline科技类
Published range国外学术期刊
Volume Issue Pagesv 9,n 2,p297-320
References
[1] Cheng, X., Du, D.Z.: Steiner Trees in Industry. Springer, Berlin (2002)
[2] Hakimi, S.L.: Steiner’s problem in graphs. Networks 1, 113–133 (1971)
[3] Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30(1), 104–114 (1976)
[4] Smith, W.D.: How to find Steiner minimal trees in Euclidean d-space. Algorithmica 7(2/3), 137–177 (1992)
[5] Johnson, D., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 760–769 (2000)
[6] Segev, A.: The node weighted Steiner tree problem. Networks 17, 1–17 (1987)
[7] Álvarez-Miranda, E., Ljubic, I., Mutzel, P.: The maximum weight connected subgraph problem. In: Jünger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 245–270. Springer, Berlin (2013)
[8] Ferreira, C.E., Filho, F.M.O.: Some formulations for the group Steiner tree problem. Electron. Notes Discr. Math. 18(1), 127–132 (2004)
[9] Salazar, J.J.: A note on the generalized Steiner tree polytope. Discr. Appl. Math. 100(1–2), 137–144 (2000)
[10] Chen, S.Y., Li, C.F., Chang, Y.W., Yang, C.L.: Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans. Comput. Aided Des. Integr. Circuit Syst. 27(4), 643–653 (2008)
[11] Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73–91 (1999)
[12] Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discr. Math. 4(3), 369–384 (1991)
[13] Kurz, D., Mutzel, P., Zey, B.: Parameterized algorithms for stochastic Steiner tree problems. Math. Eng. Methods Comput. Sci. 7721, 143–154 (2013)
[14] Voß, S.: The Steiner tree problem with hop constraints. Ann. Oper. Res. 86, 271–294 (1999)
[15] Fu, Z.H., Hao, J.K.: Breakout local search for the Steiner tree problem with revenue, budget and hop constraints. Eur. J. Oper. Res. 232(1), 209–220 (2014)
[16] Fu, Z.H., Hao, J.K.: Dynamic programming driven memetic search for the Steiner tree problem with revenue, budget and hop constraints. INFORMS J. Comput. 27(2), 221–237 (2015)
[17] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. Plenum Press, New York (1972)
[18] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
[19] Shi, W., Su, C.: The rectilinear Steiner arborescence problem is NP-complete. SIAM J. Comput. 35(3), 729–740 (2006)
[20] Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[21] Gamrath, G., Koch, T., Maher, S. T., Rehfeldt, D., Shinano, Y.: SCIP-Jack—a solver for STP and variants with parallelization extensions. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[22] Fonseca, R., Brazil, M., Winter, P., Zachariasen, M.: Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[23] El-Kebir, M., Klau, G. W.: Solving the maximum-weight connected subgraph problem to optimality. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[24] Minoux, M.: Efficient greedy heuristics for Steiner tree problems using reoptimization and supermodularity. INFOR 28, 221–233 (1990)
[25] Uchoa, E., Werneck, R.F.: Fast local search for Steiner trees in graphs. ACM J. Exp. Algorithms 17(2), 2.2:1–2.2:22 (2012)
[26] Pajor, T., Uchoa, E., Werneck, R.: A robust and scalable algorithm for the Steiner problem in graphs. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[27] Canuto, S.A., Resende, M.G.C., Ribeiro, C.C.: Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38, 50–58 (2001)
[28] Fu, Z. H., Hao, J. K.: Knowledge guided tabu search for the prize-collecting Steiner tree problem in graphs. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[29] Burdakov, O., Kvarnstrom, J., Doherty, P.: Local search heuristics for hop-constrained directed Steiner tree problem. Workshop of the 11th Dimacs Implementation Challenge, Providence, Rhode Island, December 4–5, (2014), available online at http://dimacs11.zib.de/workshop.html
[30] Hoos, H.H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco, California (2005)
[31] Johnson, D. S, Koch, T., Werneck, R. F., Zachariasen, M.: 11th DIMACS Implementation Challenge in collaboration with ICERM: Steiner tree problems. http://dimacs11.zib.de (2013–2014)
[32] Dittrich, M.T., Klau, G.W., Rosenwald, A., Dandekar, T., Müller, T.: Identifying functional modules in protein-protein interaction networks: an intergrated exact approach. Bioinformatics 24(13), i223–31 (2008)
[33] Rodriguez-Tello, E., Hao, J.K., Torres-Jimenez, J.: An improved simulated annealing algorithm for bandwidth minimization. Eur. J. Oper. Res. 185(3), 1319–1335 (2008)
[34] Rodriguez-Tello, E., Hao, J.K., Torres-Jimenez, J.: An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput. Oper. Res. 35(10), 3331–3346 (2008)
Citation statistics
Cited Times:8[WOS]   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
Identifierhttps://irepository.cuhk.edu.cn/handle/3EPUXD0A/441
CollectionInstitute of Robotics and Intelligent Manufacturing
School of Science and Engineering
Corresponding AuthorHao, Jin-Kao
Affiliation
1.Institute of Robotics and Intelligent Manufacturing, The Chinese University of Hong Kong, Shenzhen, Shenzhen; 518172, China
2.LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers Cedex 01; 49045, France
3.Institut Universitaire de France, Paris, France
First Author AffilicationInstitute of Robotics and Intelligent Manufacturing
Recommended Citation
GB/T 7714
Fu, Zhang-Hua,Hao, Jin-Kao. Swap-vertex based neighborhood for Steiner tree problems[J]. MATHEMATICAL PROGRAMMING COMPUTATION,2017.
APA Fu, Zhang-Hua, & Hao, Jin-Kao. (2017). Swap-vertex based neighborhood for Steiner tree problems. MATHEMATICAL PROGRAMMING COMPUTATION.
MLA Fu, Zhang-Hua,et al."Swap-vertex based neighborhood for Steiner tree problems".MATHEMATICAL PROGRAMMING COMPUTATION (2017).
Files in This Item:
There are no files associated with this item.
Related Services
Usage statistics
Google Scholar
Similar articles in Google Scholar
[Fu, Zhang-Hua]'s Articles
[Hao, Jin-Kao]'s Articles
Baidu academic
Similar articles in Baidu academic
[Fu, Zhang-Hua]'s Articles
[Hao, Jin-Kao]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Fu, Zhang-Hua]'s Articles
[Hao, Jin-Kao]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.