World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

THE COMPLEXITY OF THE MAXIMAL REQUESTS SATISFACTION PROBLEM IN MULTIPOINT COMMUNICATION

    A multipoint request is a group of collaborating nodes that wish to establish a communication for a certain duration of time. This need arises in parallel applications executed on processing elements connected either by specialized interconnection networks or over wide area networks (collective communication operations). Each individual request is satisfied by a given subtree connecting the participating nodes. We aim to maximize the number of requests that can be simultaneously satisfied. In this paper, we show that this problem is NP-complete and we propose for it an approximation algorithm provided that the number of requests using the same edge is bounded by a constant.

    References

    • D. Barth and P. Fragopoulou, Parallel Processing Letters 12(1), 31 (2002). LinkGoogle Scholar
    • R. B. Boppana and M. M. Halldórsson, BIT 32(2), 180 (1992). Crossref, ISIGoogle Scholar
    • D. Cavendish, A. Fei, M. Gerla, and R. Ram, "On the construction of low cost multicast trees with bandwidth reservation", In the proceedings of the High Performance Computing and Networking, 658–667, Amsterdam, NL, April 1998 . Google Scholar
    • B. Chandra and M. M. Halldórsson, Journal of Algorithms 39(2), 223 (2001). Crossref, ISIGoogle Scholar
    • P. Fragopoulou and S. G. Akl, Journal of Parallel and Distributed Computing 24(1), 55 (1995). Crossref, ISIGoogle Scholar
    • P. Fragopoulou, S. G. Akl and H. Meijer, Journal of Parallel and Distributed Computing 32(2), 173 (1996). Crossref, ISIGoogle Scholar
    • P. Fragopoulou and S. G. Akl, Parallel Computing 22(8), 991 (1996). Crossref, ISIGoogle Scholar
    • M. R.   Garey and D. S.   Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness ( W.H. Freeman and Company , 1979 ) . Google Scholar
    • M. M. Halldórsson, Journal of Graph Algorithms and Applications 4(1), 1 (2000). CrossrefGoogle Scholar
    • D. S. Hochbaum, Discrete Applied Mathematics 6, 243 (1983). Crossref, ISIGoogle Scholar
    • T. Hofmeister and H. Lefmann, "Approximating Maximum Independent Sets in Uniform Hypergraphs", Proc. of the 23rd Intl. Symp. Math. Found. of Comp. Sci. (MFCS), Lecture Notes in Computer Science, 1450:562-570, 1998 . Google Scholar
    • A. Irlande, J.-C. König, and C. Laforest, "Construction of low-cost and low-diameter steiner trees for multipoint groups", Technical Report 39-1999, LaMI, Université d'Evry, November 1999 . Google Scholar
    • M. Karpinski and A. Zelikovsky, Journal of Combinatorial Optimization 1(1), 47 (1997). Crossref, ISIGoogle Scholar
    • D. Krumme and P. Fragopoulou, Discrete Mathematics and Theoretical Computer Science 4, 157 (2001). Google Scholar
    • C. H.   Papadimitriou and K.   Steiglitz , Combinatorial optimization: algorithms and complexity ( Prentice Hall , 1982 ) . Google Scholar
    • V. Th. Paschos, ACM Computing Surveys 29(2), 171 (1997). Crossref, ISIGoogle Scholar
    • T. Vorakosit and P. Uthayopas, "Generating an Efficient Dynamics Multicast Tree under Grid Environment", in Proceedings of the 10th European PVM/MPI User's Group Meeting, Venice, IT, Sept. 2003, Lecture Notes in Computer Science, 2840:636–643, 2003 . Google Scholar
    • Gill Waters, John Crawford and Sei Guan Lim, Computer Communications 27, 1389 (2004). Crossref, ISIGoogle Scholar
    • B. Y. Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, and C. Y. Tan, "A polynomial time approximation scheme for minimum routing cost spanning trees", in the proceedings of the ACM Symposium On Discrete Algorithms, 21–32, San Francisco, CA, January 1998 . Google Scholar