Minimal Threshold Separators and Memory Requirements for Synchronization

DOI10.1137/0218010zbMath0677.68064OpenAlexW2013245663MaRDI QIDQ3833628

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

threshold graphmutual exclusiontest-and-setsynchronization primitivesPV-chunk

Mathematics Subject Classification ID

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

Related Items

Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ An \(O(n^ 3)\) recognition algorithm for bithreshold graphs