Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs

DOI10.1016/0304-3975(91)90265-4zbMath0752.68046OpenAlexW2043055902MaRDI QIDQ1183585

S. Singh

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90265-4

zbMATH Keywords

polynomial time algorithmparallel algorithmEREW PRAMpermutation graphdominating clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

On-line algorithms for the dominating set problem ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• On domination problems for permutation and other graphs
• An efficient parallel algorithm for updating minimum spanning trees
• An efficient algorithm for maxdominance, with applications
• Searching, Merging, and Sorting in Parallel Computation
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Merge Sort
• Parallel Prefix Computation

This page was built for publication: Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs