Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
International Journal of Parallel Programming
Erschienen in: International Journal of Parallel Programming 2/2014

01.04.2014

A Survey of Parallel and Distributed Algorithms for the Steiner Tree Problem

verfasst von: Mitja Bezenšek, Borut Robič

Erschienen in: International Journal of Parallel Programming | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given a set of input points, the Steiner Tree Problem (STP) is to find a minimum-length tree that connects the input points, where it is possible to add new points to minimize the length of the tree. Solving the STP is of great importance since it is one of the fundamental problems in network design, very large scale integration routing, multicast routing, wire length estimation, computational biology, and many other areas. However, the STP is NP-hard, which shatters any hopes of finding a polynomial-time algorithm to solve the problem exactly. This is why the majority of research has looked at finding efficient heuristic algorithms. Additionally, many authors focused their work on utilizing the ever-increasing computational power and developed many parallel and distributed methods for solving the problem. In this way we are able to obtain better results in less time than ever before. Here, we present a survey of the parallel and distributed methods for solving the STP and discuss some of their applications.
Vorheriger Artikel The Experience in Designing and Evaluating the High Performance Cluster Netuno
Nächster Artikel A Case Study of Implementing Supernode Transformations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Du, D.Z., Rubensteiner, J.H., Smith, J.M.: Advances in Steiner trees. In: Combinatorial Optimization, vol. 6. Kluwer Academic Publishers, Dordrecht (2000)
2.
Prömel, H.J., Steger, A.: The Steiner tree problem. Friedrick Vieweg and Son, Germany (2002)CrossRefMATH
3.
Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: SODA ’00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and, Applied Mathematics, pp. 770–779 (2000)
4.
5.
Gröpl, C., Hougardy, S., Nierhoff, T., Prömel, H.J.: Approximation algorithms for the Steiner tree problem in graphs. In: Combinatorial Optimization, vol. 11. Kluwer Academic Publishers, Dordrecht (2002)
6.
Warme, D.M., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: a computational study. Kluwer Academic Publishers, Dordrecht (2000)
7.
8.
9.
Berman, P., Ramaiye, V.: Improved approximations for the Steiner tree problem. In: SODA ’92: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and, Applied Mathematics, pp. 325–334 (1992)
10.
Zelikovsky, A.: Better approximation bounds for the network and Euclidean Steiner tree problems. Technical report, University of Virginia, Charlottesville, VA, USA (1996)
11.
Prömel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. J. Algorithms 36(1), 89–101 (2000)CrossRefMATHMathSciNet
12.
13.
Hougardy, S., Prömel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: SODA ’99: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and, Applied Mathematics, pp. 448–453 (1999)
14.
15.
Du, D., Hu, X.: Steiner tree problem in computer communication networks. World Scientific, Singapore (2008)CrossRef
16.
Du, D.Z., Zhang, Y., Feng, Q.: On better heuristic for Euclidean Steiner minimum trees. In: Proceedings 32nd Annual Symposium of Foundations of Computer Science. pp. 431–439 (1991)
17.
Zelikovsky, A.: An 11/8-approximation algorithm for the Steiner problem on networks with rectilinear distance. Coll. Math. Soc. Janos Bolyai 60, 733–745 (1992)MathSciNet
18.
Martins, S.L., Ribeiro, C.C., Souza, M.C.: A parallel GRASP for the Steiner problem in graphs. In: IRREGULAR ’98: Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel, pp. 285–297 (1998)
19.
Resende, M., Pardalos, P., Eksioglu, S.D.: Parallel metaheuristics for combinatorial optimization. Kluwer Academic Publishers, Dordrecht (1999)
20.
Kruskal Jr, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50 (1956)CrossRefMATHMathSciNet
21.
Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389–1401 (1957)CrossRef
22.
Du, D.Z., Hwang, F.K.: A proof of Gilbert and Pollak’s conjecture on the Steiner ratio. Algorithmica 7(2/3), 121–135 (1992)CrossRefMATHMathSciNet
23.
Du, D.Z., Smith, W.D.: Disproofs of generalized Gilbert-Pollak conjecture on the Steiner ratio in three or more dimensions. J. Comb. Theory Ser. A 74, 115–130 (1996)CrossRefMATHMathSciNet
24.
Innami, N., Kim, B., Mashiko, Y., Shiohama, K.: The Steiner ratio conjecture of Gilbert-Pollak may still be open. Algorithmica 57, 869–872 (2008)
25.
Smith, W.D., Smith, J.M.G.: On the Steiner ratio in 3-space. J. Comb. Theory Ser. A 69(2), 301–332 (1995)CrossRefMATH
26.
27.
28.
Zachariasen, M.: Algorithms for plane Steiner tree problems. Ph. d. University of Copenhagen (1998)
29.
Harris Jr, F.C.: Steiner minimal trees: their computational past, present, and future. J. Comb. Math. Combin. Comput. 30, 195–220 (1998)
30.
Vazirani, V.V.: Approximation algorithms. Springer, Berlin (2001)
31.
Courant, R., Robbins, H.: What is mathematics? Oxford University Press, Oxford (1941)
32.
Hwang, F.K., Richards, D.S., Winter, P.: The Steiner tree problem. North Holland, Amsterdam (1992)MATH
33.
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
34.
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. JACM 45(5), 753–782 (1998)CrossRefMATH
35.
Ivanov, A.O., Tuzhilin, A.A.: Geometry of minimal networks and the one-dimensional Plateau problem. Russ. Math. Surv. 47(2), 59–131 (1992)CrossRefMathSciNet
36.
Nelson, N.M., Michelon, P., Adilson, X.: The Euclidean Steiner tree problem in Rn: a mathematical programming formulation. Ann. Oper. Res. 96(12), 209–220 (2000)MathSciNet
37.
38.
Simchi-Levi, D., Bienstock, D., Goemans, M.X., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993)CrossRefMATHMathSciNet
39.
Xu, J., Hong, Y., Jing, T., Yang, Y.: Obstacle-avoiding rectilinear minimum-delay Steiner tree construction towards IP-block-based SOC design. In: ISQED ’05: Proceedings of the 6th International Symposium on Quality of Electronic Design, pp. 616–621. IEEE Computer Society (2005)
40.
Akbari, H., Iranmanesh, Z., Ghodsi, M.: Parallel Minimum Spanning Tree Heuristic for the Steiner problem in graphs. In: 2007 International Conference on Parallel and Distributed Systems, pp. 1–8 (2007)
41.
Coulston, C.S.: Constructing exact octagonal Steiner minimal trees. In: GLSVLSI ’03: Proceedings of the 13th ACM Great Lakes Symposium on VLSI, ACM, pp. 1–6 (2003)
42.
Du, D.Z., Wang, L., Xu, B.: The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In: COCOON ’01: Proceedings of the 7th Annual International Conference on Computing and Combinatorics, pp. 509–518. Springer, Berlin (2001)
43.
Even, G., Kortsarz, G., Slany, W.: On network design problems: fixed cost flows and the covering steiner problem. ACM Trans. Algorithms 1(1), 74–101 (2005)CrossRefMathSciNet
44.
45.
Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37, 66–84 (2000)CrossRefMATHMathSciNet
46.
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., San Francisco, CA (1990)
47.
48.
Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Dover Publications, New York (1998)MATH
49.
Rao, S.B., Smith, W.D.: Approximating geometrical graphs via “spanners” and “banyans”. In: STOC ’98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 540–550. ACM (1998)
50.
Borradaile, G., Klein, P.N., Mathieu, C.: Steiner tree in planar graphs: an O(n log n) approximation scheme with singly-exponential dependence on epsilon. ACM Trans. Algorithms 5(3), 1–31 (2007)CrossRefMathSciNet
51.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 2nd edn. McGraw-Hill Science/Engineering/Math, New York (2001)MATH
52.
Takahashi, H., Matsuyama, A.: An approximation solution for the Steiner tree problem in graphs. Math. Jpn. 24, 573–577 (1982)MathSciNet
53.
Bauer, F., Varma, A.: Distributed algorithms for multicast path setup in data networks. IEEE/ACM Trans. Netw. 4(2), 181–191 (1996)CrossRef
54.
Rayward-Smith, V.J.: The computation of nearly minimal Steiner trees in graphs. Internat. J. Math. Educ. Sci. Technol. 14, 15–23 (1983)CrossRefMATHMathSciNet
55.
56.
Esbensen, H.: Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm. Networks 26, 173–185 (1995)CrossRefMATH
57.
Kapsalis, A., Smith, G.D., Rayward-Smith, V.J.: Solving the graphical Steiner tree problem using genetic algorithms. J. Oper. Res. Soc. 26, 173–185 (1993)
58.
Duin, C.W., Voß, S.: Efficient path and vertex exchange in Steiner tree algorithms. Networks 29, 89–105 (1995)CrossRef
59.
Xu, J., Chiu, S.Y., Glover, F.: Probabilistic tabu search for telecommunications network design. J. Comb. Optim. 1, 69–94 (1996)
60.
Xu, J., Chiu, S., Glover, F.: Using tabu search to solve Steiner tree-star problem in telecommunications network design. Telecommun Syst 6, 117–125 (1996)CrossRef
61.
Martins, S.L., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Quadratic assignment and related problems. In: DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 16, pp. 237–261. American Mathematical Society (1994)
62.
Dowsland, K.A.: Hill-climbing simulated annealing and the Steiner problem in graphs. Eng. Optim. 17, 91–107 (1991)CrossRef
63.
Holland, J.: Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI (1975)
64.
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986)CrossRefMATHMathSciNet
65.
66.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087–1092 (1953)CrossRef
67.
Rugelj, J., Novak, R., Kandus, G.: Steiner tree based distributed multicast routing in networks, vol. 11. Kluwer Academic Publishers, Dordrecht (2000)
68.
Oliveira, C., Pardalos, P.: A survey of combinatorial optimization problems in multicast routing. Comput. Oper. Res. 32(8), 1953–1981 (2005)CrossRefMATH
69.
Oliveira, C.A.S., Pardalos, P.M.: Mathematical Aspects of Network Routing Optimization, vol. 53. Springer, Berlin (2011)CrossRefMATH
70.
Kompella, V.P., Pasquale, J.C., Polyzos, G.C.: Two distributed algorithms for multicasting multimedia information. IEE/ACM Trans. Netw. 1, 286–292 (1993)CrossRef
71.
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5, 66–77 (1983)CrossRefMATH
72.
Novak, R., Rugelj, J.: Distribution of constrained Steiner tree computation in shortest-delay networks. In: MELECON’96, 8th Mediterranean Electrotechnical Conference, vol. 2, pp. 0–3 (1996)
73.
Rugelj, J.: Distributed multicast routing mechanism for global point-to-point networks. In: Proceedings of Twentieth Euromicro Conference, System Architecture and Integration, pp. 389–395 (1994)
74.
75.
Gatani, L., Lo Re, G., Gaglio, S.: An efficient distributed algorithm for generating and updating multicast trees. Parallel Comput. 32(11–12), 777–793 (2006)CrossRef
76.
Singh, G., Vellanki, K.: A distributed protocol for constructing multicast trees. In: 2nd International Conference On Principles Of Distributed Systems (OPODIS’98), pp. 61–76 (1998)
77.
Kun, Z., Yong, Q., Hong, Z.: Dynamic multicast routing algorithm for delay and delay variation-bounded Steiner tree problem. Knowl Based Syst. 19(7), 554–564 (2006)CrossRef
78.
Wong, RichardT: A dual ascent approach for steiner tree problems on a directed graph. Math. Program. 28(3), 271–287 (1984)CrossRefMATH
79.
80.
Drummond, L.M.A., Santos, M., Uchoa, E.: A distributed dual ascent algorithm for Steiner problems in multicast routing. Network 53, 170–183 (2009)CrossRefMATHMathSciNet
81.
Shen, C.C., Li, K., Jaikaeo, C., Sridhara, V.: Ant-based distributed constrained steiner tree algorithm for jointly conserving energy and bounding delay in ad hoc multicast routing. ACM Trans. Auton. Adapt. Syst. 3(1), 1–27 (2008)CrossRef
82.
Torkestani, J.A., Meybodi, M.R.: Weighted Steiner connected dominating set and its application to multicast routing in wireless MANETs. Wirel. Pers. Commun. 60(2), 145–169 (2010)CrossRef
83.
84.
Drummond, L., Uchoa, E., Goncalves, A., Silva, J., Santos, M., Decastro, M.: A grid-enabled distributed branch-and-bound algorithm with application on the Steiner problem in graphs. Parallel Comput. 32(9), 629–642 (2006)CrossRefMathSciNet
85.
Kesselman, C., Foster, I.: The grid: blueprint for a new computing infrastructure. Morgan Kaufmann Publishers, Florida (1998)
86.
Uchoa, E.: Algoritmos para problemas de Steiner com aplicaçaõ em projeto de circuitos VLSI. Ph. d. Catholic Universtiy of Rio de Janeiro (2001)
87.
Zhou, H.: Efficient Steiner tree construction based on spanning graphs. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 23(5), 704–710 (2004)CrossRef
88.
Kahng, A., Robins, G.: A new class of Steiner tree heuristics with good performance: the iterated 1-Steiner approach. In: IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, pp. 428–431 (1990)
89.
Cinel, S., Bazlamacci, C.F.: A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem. Comput. Aided Des. 27(11), 2083–2087 (2008)
90.
91.
92.
Harris, Jr. F.C.: Parallel computation of steiner minimal trees. In: Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing, pp. 267–272 (2007)
93.
Park, J.S., Ro, W.W., Lee, H., Park, N.: Parallel Algorithms for Steiner Tree Problem. In: 2008 Third International Conference on Convergence and Hybrid Information Technology, pp. 453–455 (2008)
94.
Jayaraman, R., Rutenbar, R.A.: A parallel Steiner heuristic for wirelength estimation of large net populations. In: 1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers, pp. 344–347 (1991)
95.
Dunlop, A.E., Kernighan, B.W.: A procedure for placement of standard-cell VLSI circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 4, 92–98 (1985)CrossRef
96.
McKee, S.A., Barrera, T., Griffith, J., Robins, G., Zhang, T.: Toward a Steiner engine: enhanced serial and parallel implementations of the iterated 1-Steiner MRST algorithm. In: Proceedings of the Third Great Lakes Symposium on VLSI-Design Automation of High Performance VLSI Systems, vol. 2442, pp. 90–94 (1993)
97.
Spoon, S.A.: A Parallel Branch-and-Bound Algorithm for Finding Steiner Minimal Trees (1996)
98.
Pargas, R.P., Ludwick, J., Spoon, S.: Hybrid search algorithms. In: SAC ’97: Proceedings of the 1997 ACM symposium on Applied Computing, pp. 269–273 (1997)
99.
Verhoeven, M.G.A., Severens, M.E.M.: Parallel local search. J. Heuristics 1, 43–65 (1995)CrossRefMATH
100.
Voß, S.: Steiner’s problem in graphs: heuristic methods. Discret. Appl. Math. 40, 45–72 (1992)CrossRefMATH
101.
Leighton, F.T.: Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Mateo, CA (1992)
102.
Fobel, C., Grewal, G.: A parallel Steiner tree heuristic for macro cell routing. In: IEEE International Conference on Computer Design, vol. 27–33 (2008)
103.
Ludwick, J.: A parallel and genetic approach to the Steiner tree extraction problem. Masters, Clemson University, Clemson, South Carolina (1996)
104.
Bastos, M.P., Ribeiro, C.C.: Reactive tabu search with path-relinking for the Steiner problem in graphs. In: Proceedings of the Third Metaheuristics International Conference, pp. 31–36 (1999)
105.
106.
Martins, S.L., Resende, M.G.C., Ribeiro, C.C., Pardalos, P.M.: A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. J. Global Optim. 17(1), 267–283 (2000)CrossRefMATHMathSciNet
107.
Di Fatta, G., Presti, G.L., Presti, G.L., Re, G.L., Re, G.L.: A parallel genetic algorithm for the steiner problem in networks. In: Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2003) vol. 2, pp. 569–573 (2003)
108.
Presti, G.L., Re, G.L., Storniolo, P., Urso, A.: A grid enabled parallel hybrid genetic algorithm for SPN. In: ICCS: Lecture Notes in Computer Science. Springer, pp. 156–163 (2004)
109.
Muhmmad, R.B.: Parallelization of local search for Euclidean Steiner tree problem. In: Proceedings of the 44th Annual Southeast Regional Conference on - ACM-SE 44, pp. 233–238 (2006)
110.
Zachariasen, M.: Local search for the Steiner tree problem in the Euclidean plane. Eur. J. Oper. Res. 119(2), 282–300 (1999)CrossRefMATHMathSciNet
111.
Handa, Y., Ono, H., Sadakane, K., Yamashita, M.: Neighboorhood composition: a parallelization of local search algorithms. Springer, Berlin (2004)
112.
Totsukawa, H., Senou, H., Ohmura, M.: A parallel genetic algorithm for 3-D rectilinear Steiner tree with bounded number of bends. In: 2008 51st Midwest Symposium on Circuits and Systems, pp. 89–92 (2008)
113.
Huy, N.V., Nghia, N.D.: Solving graphical Steiner tree problem using parallel genetic algorithm. In: IEEE International Conference on Research, Innovation, pp. 29–35 (2008)
114.
Bouchachia, A., Prossegger, M.: A hybrid ensemble approach for the Steiner tree problem in large graphs: a geographical application. Appl. Soft Comput. 11(8), 5745–5754 (2011)CrossRef
115.
Chamberlain, B.: Graph partitioning algorithms for distributing workloads of parallel computations. Technical report (1998)
116.
117.
Beasley, J.E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990)
118.
Zhao, J., Chen, C., Ahmadi, M.: Probability-based approach to rectilinear Steiner tree problems. IEEE Trans. VLSI Syst. 10, 836–843 (2002)CrossRef
119.
Muhmmad, R.B.: Distributed Steiner tree algorithm and its application in ad hoc wireless networks. In: Proceedings of the 2006 International Conference on Wireless Networks (ICWN’06), pp. 173–178 (2006)
120.
Ilyas, M.: The handbook of ad hoc wireless networks. CRC Press, Inc., Boca Raton, FL (2003)
121.
Lin, G.H., Jiang, T., Kearney, P.E.: Phylogenetic k-Root and Steiner k-Root. Lecture notes in computer science, pp. 539–551 (2000)
122.
Lu, C.L., Tang, C.Y., Lee, R.C.T.: The full Steiner tree problem in phylogeny. In: COCOON ’02: Proceedings of the 8th Annual International Conference on Computing and Combinatorics, pp. 107–116. Springer, London (2002)
123.
Fernández-Baca, D.: The perfect phylogeny problem. In: Du, D.Z., Pardalos, P.M. (eds.) Steiner Trees in Industry. Combinatorial Optimization, vol. 11, pp. 203–234. Kluwer Academic Publishers (2004)
Metadaten
Titel
A Survey of Parallel and Distributed Algorithms for the Steiner Tree Problem
verfasst von
Mitja Bezenšek
Borut Robič
Publikationsdatum
01.04.2014
Verlag
Springer US
Erschienen in
International Journal of Parallel Programming / Ausgabe 2/2014
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI
https://doi.org/10.1007/s10766-013-0243-z

Weitere Artikel der Ausgabe 2/2014

International Journal of Parallel Programming 2/2014 Zur Ausgabe

OriginalPaper

Parallelization of Full Search Motion Estimation Algorithm for Parallel and Distributed Platforms

OriginalPaper

Boosting CUDA Applications with CPU–GPU Hybrid Computing

Announcement

Editor’s Note

OriginalPaper

Automatic Skeleton-Driven Memory Affinity for Transactional Worklist Applications

Erratum

Erratum to: Accelerating Single Iteration Performance of CUDA-Based 3D Reaction–Diffusion Simulations

OriginalPaper

The Experience in Designing and Evaluating the High Performance Cluster Netuno