APPROXIMATION ALGORITHMS FOR SP-MULTICAST TREES IN 2D GRIDS1

Teofilo F. Gonzalez

References

  1. [1] T.F. Gonzalez, SP-multicasting trees for grids, Proceedings ofthe 23rd IASTED PDCS ’11, Dallas Texas, 2011.
  2. [2] R.R. Ladeira de Matos, A rectilinear arborescence problem,Ph.D. Dissertation, University of Alabama, Tuscaloosa, AL,1979.
  3. [3] L. Nastansky, S.M. Selkow, and N.F. Stewart, Cost-minimaltrees in directed acyclic graphs, Zeitschrift fuer OperationResearch, 18, 1974, 59–67.
  4. [4] V.A. Trubin, Subclass of the Steiner problems on a plane withrectilinear metric, Cybernetics, 21, 1985, 320–322, translatedfrom Kibernetika, 21, 1985, 33–40.
  5. [5] S.K. Rao, P. Sadayappan, F.K. Hwang, and P.W. Shor, Therectilinear Steiner arborescence problem, Algorithmica, 7, 1992,277–288.
  6. [6] W. Shi and C. Su, The rectilinear Steiner arborescence problemis NP-complete, SIAM Journal on Computing, 35(3), 2006,729–740.
  7. [7] S. Ramnath, New approximations for the rectilinear Steinerarborescence problem, IEEE Transactions on CAD, 22(7),2003, 859–869.
  8. [8] B. Lu and L. Ruan, Polynomial time approximation schemefor the rectilinear Steiner tree arborescence problem, Journalof Combinatorial Optimization, 4, 2000, 357–363.
  9. [9] N. Robertson, D.P. Sanders, P. Seymour, and R. Thomas, Thefour-colour theorem, Journal of Combinatorial Theory SeriesB, 70(1), 1997, 2–44.
  10. [10] F. Hadlock, Finding a maximum cut of a planar graph inpolynomial time, SIAM Journal on Computing, 4(3), 1975.
  11. [11] F. Liers and G. Pardella, A fast max-cut algorithm on planargraphs, 13th Combinatorial Optimization Workshop, Aussois,2008.

Important Links:

Go Back