CHEN Fang gan, SUN Liang. On the Complexity and Algorithm of Optional Dominating Set on Planar GraphsJ. Transactions of Beijing institute of Technology, 2003, (3): 274-276.
Citation:
CHEN Fang gan, SUN Liang. On the Complexity and Algorithm of Optional Dominating Set on Planar GraphsJ. Transactions of Beijing institute of Technology, 2003, (3): 274-276.
CHEN Fang gan, SUN Liang. On the Complexity and Algorithm of Optional Dominating Set on Planar GraphsJ. Transactions of Beijing institute of Technology, 2003, (3): 274-276.
Citation:
CHEN Fang gan, SUN Liang. On the Complexity and Algorithm of Optional Dominating Set on Planar GraphsJ. Transactions of Beijing institute of Technology, 2003, (3): 274-276.
On the Complexity and Algorithm of Optional Dominating Set on Planar Graphs
Optional dominating set on planar graphs is studied. By a transformation from PX3C to dominating set on planar graphs, the paper shows that the problem of decision of dominating set on planar graphs is NP complete. The NP completeness of optional dominating set on planar graphs is thus proved. A proximate algorithm based genetic algorithm on the problem is thereby proposed.
DownLoad: