NP-Completeness in the gossip monoid

DOI10.1142/S0218196718500297zbMath1498.20137arXiv1606.01026OpenAlexW2963266480MaRDI QIDQ4576008

Marianne Johnson, Peter Fenner, Mark Kambites

Publication date: 12 July 2018

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.01026

zbMATH Keywords

computational complexitynetworkssemigroup theorygossip

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Identities of the stylic monoid ⋮ Identities in unitriangular and gossip monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs, networks and algorithms.
• Double Catalan monoids
• On maximal subgroups of free idempotent generated semigroups.
• Free idempotent generated semigroups and endomorphism monoids of free \(G\)-acts.
• Lossy gossip and composition of metrics
• Subgroups of free idempotent generated semigroups need not be free.
• Gossips and telephones
• On the structure of semigroups
• Maximal subgroups of free idempotent generated semigroups over the full linear monoid
• Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid
• A Cure for the Telephone Disease