Minimal Threshold Separators and Memory Requirements for Synchronization

DOI10.1137/0218010MaRDI QIDQ3833628zbMATH OpenOpenAlexFDO

Authors Edward T. Ordman

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218010

zbMATH Keywords

mutual exclusionPV-chunksynchronization primitivestest-and-setthreshold graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Theory of computing (68Q99) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• ON PV_chunk OPERATIONS AND MATROGENIC GRAPHS
• scientific article; zbMATH DE number 4043213
• Bounds on shared memory for mutual exclusion
• On the mutual-exclusion problem -- a quest for minimal solutions
• A technique for decomposing algorithms which use a single shared variable

Cited in

(6)

• Minimizing synchronization in \(\text{IDR}(s)\).
• scientific article; zbMATH DE number 4043213 (Why is no real title available?)
• ON PV_chunk OPERATIONS AND MATROGENIC GRAPHS
• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
• Threshold graphs and synchronization protocols
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs

This page was built for publication: Minimal Threshold Separators and Memory Requirements for Synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3833628)