The minimum weight dominating set problem for permutation graphs is in NC

DOI10.1006/jpdc.1995.1093zbMath0833.68068OpenAlexW2005990507MaRDI QIDQ1898177

S. Lakshmivarahan, Chongkye Rhee, Sudarshan K. Dhall

Publication date: 24 September 1995

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jpdc.1995.1093

zbMATH Keywords

CRCW model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Parallel algorithms for the domination problems in trapezoid graphs, A new approach for the domination problem on permutation graphs