Local Optimality and Its Application on Independent Sets for k-claw Free Graphs

Gang Yu and Olivier Goldschmidt
Additional contact information
Gang Yu: The University of Texas at Austin
Olivier Goldschmidt: The University of Texas at Austin

Journal of Combinatorial Optimization, 1997, vol. 1, issue 2, No 3, 164 pages

Abstract: 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 ∩ 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.

Keywords: local optimality; approximation algorithms; combinatorial optimization (search for similar items in EconPapers)
Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009755815678 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:1:y:1997:i:2:d:10.1023_a:1009755815678

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009755815678

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().