{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T12:10:02Z","timestamp":1723205402988},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>The reconfigurable mesh (RN\u2010MESH) can solve a large class of problems in constant\ntime, including problems that require logarithmic time by other, even shared memory,\nmodels such as the PRAM with a similar number of processors [3]. In this work we show\nthat for the RN\u2010MESH these constants can always be reduced to one, still using a\npolynomial number of processors. Given a reconfigurable mesh that computes a set of\nvalues in constant time, we show that it can be simulated by a single step reconfigurable\nmesh with maximum size that is polynomial in the size of the original mesh. The proof is\nconstructive, where the construction of the single step RN\u2010MESH holds for the\nrelatively weak undirected RN\u2010MESH model. In this model broadcasts made on buses\narrive at all nodes that belong to the undirected connected component of the\ntransmitting processor. A result similar to the one that is obtained in this work was\npreviously obtained for the directed reconfigurable mesh model (DRN) [5]. However,\nthe construction for the DRN\u2010MESH relies on the fact that the buses are directed, and\nthus cannot be applied to the undirected case. In addition, the construction presented\nhere is simpler and uses significantly fewer processors than the one obtained for the\nDRN\u2010MESH.<\/jats:p>","DOI":"10.1155\/1999\/71739","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:58:21Z","timestamp":1190120301000},"page":"17-28","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Single Step Undirected Reconfigurable Networks"],"prefix":"10.1155","volume":"9","author":[{"given":"Yosi","family":"Ben-Asher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1999,1]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1999\/071739.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1999\/71739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T11:52:15Z","timestamp":1723204335000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1999\/71739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1155\/1999\/71739"],"URL":"https:\/\/doi.org\/10.1155\/1999\/71739","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1999,1]]},"assertion":[{"value":"1997-05-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"1999-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}