Utilizza questo identificativo per citare o creare un link a questo documento:
|Titolo:||Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs|
|Autori interni:||Cicalese, Ferdinando|
|Data di pubblicazione:||2011|
|Abstract:||We consider two graph optimization problems called vector domina- tion 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 vector domination, the requirement is extended to all vertices of the graph. We prove that these problems cannot be approximated to within a factor of clogn, for suitable constants c, unless every problem in NP is solvable in slightly super-polynomial time. We also show that two natural greedy strategies have approximation factors O(log Δ(G)), where Δ(G) is the maximum degree of the graph G. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature.|
|Appare nelle tipologie:||04.01 Contributo in atti di convegno|
File in questo prodotto:
Non ci sono file associati a questo prodotto.
- PubMed Central loading...
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.