{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T22:52:08Z","timestamp":1648594328483},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0129626405002167","type":"journal-article","created":{"date-parts":[[2005,7,21]],"date-time":"2005-07-21T22:53:58Z","timestamp":1121986438000},"page":"209-222","source":"Crossref","is-referenced-by-count":0,"title":["THE COMPLEXITY OF THE MAXIMAL REQUESTS SATISFACTION PROBLEM IN MULTIPOINT COMMUNICATION"],"prefix":"10.1142","volume":"15","author":[{"given":"DOMINIQUE","family":"BARTH","sequence":"first","affiliation":[{"name":"Laboratoire de Research en Informatique  PRiSM, Universit\u00e9 de Versailles St-Quentin en Yvelines,  45 Avenue des Etats-Unis, 78035 Versailles Cedex, France"}]},{"given":"PASCAL","family":"BERTHOME","sequence":"additional","affiliation":[{"name":"Laboratoire de Research en  Informatique LRI, B\u00e2t 490, Universit\u00e9 Paris-Sud,  91405 Orsay Cedex, France"}]},{"given":"PARASKEVI","family":"FRAGOPOULOU","sequence":"additional","affiliation":[{"name":"Department of Applied Informatics  and Multimedia, Technological Educational Institute of Crete,  P.O. Box 1939, GR-71004 Heraklion-Crete, Greece"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1142\/S012962640200080X"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994876"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1155"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1006"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0012"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(96)00029-4"},{"key":"rf8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90080-X"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"rf14","first-page":"157","volume":"4","author":"Krumme D.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"rf15","volume-title":"Combinatorial optimization: algorithms and complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1145\/254180.254190"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2004.02.015"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626405002167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:14:35Z","timestamp":1565093675000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626405002167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":14,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1142\/S0129626405002167"],"URL":"https:\/\/doi.org\/10.1142\/s0129626405002167","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]}}}