| Autor: | Gang Yu, Olivier Goldschmidt |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics Control and Optimization Applied Mathematics Approximation algorithm Graph Computer Science Applications Combinatorics Minimum dominating set Computational Theory and Mathematics Bounded function Independent set Discrete Mathematics and Combinatorics Combinatorial optimization Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 1:151-164 |
| ISSN: | 1382-6905 |
| DOI: | 10.1023/a:1009755815678 |
| Popis: | 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 ∩ T = ∅ and Γ(S) \( \subseteq \) T, where Γ(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 ∩ Γ(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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|