Name
Abstract | ||
|---|---|---|
Given a graph G = (V,E), we define the locally optimal independent sets asfollows. Let S be an independent set and T be a subset of V such that S n T = Ø and G(S)
$$ \subseteq $$
T, where G(S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as TD(S)
$$ \subseteq $$
T such that every vertex of S is adjacent to a vertex inTD(S) and TD(S) has minimum cardinality. An independent setI is called r-locally optimal if it is maximal and there exists noindependent set S
$$ \subseteq $$
V\I with |ID (S)| = r such that|S| >|I n G(S)|.In this paper, we demonstrate that for k-claw free graphs ther-locally optimal independent sets is found in polynomial timeand the worst case is bounded by
$$\left| {I*} \right| \leqslant \frac{1}{2}\left[ {\frac{1}{{\sum _{i = 1}^r (k - 2)^{i - 1} }} + k - 1} \right]\left| I \right|$$
, where I and I* are a locally optimal and an optimal independent set,respectively. This improves the best published bound by Hochbaum (1983) bynearly a factor of two. The bound is proved by LP duality and complementaryslackness. We provide an efficientO(|V|r+3) algorithm to find an independent set which is notnecessarily r-locally optimal but is guarantteed with the above bound. Wealso present an algorithm to find a r-locally optimal independent set inO(|V|r(k-1)+3) time. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1023/A:1009755815678 | J. Comb. Optim. |
Keywords | Field | DocType |
local optimality,approximation algorithms,combinatorial optimization | Approximation algorithm,Discrete mathematics,Mathematical optimization,Combinatorics,Vertex (geometry),Polynomial,Cardinality,Combinatorial optimization,Independent set,Duality (optimization),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
1 | 2 | 1573-2886 |
Citations | PageRank | References |
3 | 0.86 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gang Yu | 1 | 3 | 0.86 |
| Olivier Goldschmidt | 2 | 3 | 0.86 |