The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC.
Chong Jye RheeSudarshan K. DhallS. LakshmivarahanPublished in: J. Parallel Distributed Comput. (1995)
Keyphrases
- minimum weight
- dominating set
- connected dominating set
- bipartite graph
- weighted graph
- maximum cardinality
- spanning tree
- facility location problem
- minimum spanning tree
- planar graphs
- edge weights
- greedy heuristic
- randomized algorithm
- undirected graph
- graph theory
- facility location
- computational complexity
- tree patterns
- greedy algorithm
- upper bound
- np hard