{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,9]],"date-time":"2022-08-09T17:29:19Z","timestamp":1660066159669},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set of all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years. <\/jats:p>","DOI":"10.1142\/s0218196718500297","type":"journal-article","created":{"date-parts":[[2018,4,23]],"date-time":"2018-04-23T04:31:08Z","timestamp":1524457868000},"page":"653-672","source":"Crossref","is-referenced-by-count":2,"title":["NP-Completeness in the gossip monoid"],"prefix":"10.1142","volume":"28","author":[{"given":"Peter","family":"Fenner","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Manchester, Manchester M13 9PL, England"}]},{"given":"Marianne","family":"Johnson","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Manchester, Manchester M13 9PL, England"}]},{"given":"Mark","family":"Kambites","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Manchester, Manchester M13 9PL, England"}]}],"member":"219","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"S0218196718500297BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90001-5"},{"key":"S0218196718500297BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.12.017"},{"key":"S0218196718500297BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9666-1"},{"key":"S0218196718500297BIB004","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/007.1"},{"key":"S0218196718500297BIB005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05864-3"},{"key":"S0218196718500297BIB007","volume-title":"Computers and Intractability: A Guide to NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0218196718500297BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0154-x"},{"key":"S0218196718500297BIB009","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdr054"},{"key":"S0218196718500297BIB010","doi-asserted-by":"publisher","DOI":"10.2307\/1969317"},{"key":"S0218196718500297BIB011","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1972-081-0"},{"key":"S0218196718500297BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32278-5"},{"key":"S0218196718500297BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-011-0336-y"},{"issue":"3","key":"S0218196718500297BIB014","first-page":"188","volume":"19","author":"Tijdeman R.","year":"1971","journal-title":"Nieuw Arch. Wiskd."},{"key":"S0218196718500297BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2014.12.041"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196718500297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:45:50Z","timestamp":1565106350000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196718500297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":14,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,28]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0218196718500297"],"URL":"https:\/\/doi.org\/10.1142\/s0218196718500297","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}