Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs

Details Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs

2010-12-07

arxiv.org/abs/1012.1529v1

Computer Science

Discrete Mathematics

Scientific paper

We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset $S$ of vertices of a graph such that any vertex outside $S$ has a prescribed number of neighbors in $S$. In total domination, the requirement is extended to all vertices of the graph. We prove that these problems cannot be approximated to within a factor of $c\log n$, for suitable constant $c$, unless every problem in NP is solvable in slightly super-polynomial time. We also show that two natural greedy strategies have approximation factor $O(\log \Delta(G))$, where $\Delta(G)$ is the maximum degree of the graph $G$. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend and unify several results previously known in the literature.

Affiliated with

Also associated with

No associations

Rating

Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-481098