Premium
On locally optimal independent sets and vertex covers
Author(s) -
Yu Gang,
Goldschmidt Olivier
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199608)43:5<737::aid-nav9>3.0.co;2-6
Subject(s) - vertex (graph theory) , independent set , clique , heuristic , mathematical optimization , mathematics , steiner tree problem , set (abstract data type) , computer science , vertex cover , graph , combinatorics , approximation algorithm , programming language
In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k ‐claw free graphs. The maximum independent set problem in k ‐claw free graphs has interesting applications in the design of electronic testing fixtures for printed circuit boards [13]. For this problem, our concept of local optimality enabled us to devise an efficient heuristic algorithm which outperforms the currently best approximation algorithm by nearly a factor of two in terms of worst case bound. We believe that the idea of local optimality suggested in this paper can also be applied to other combinatorial problems such as the clique problem, the dominating set problem and the graph coloring problem. © 1996 John Wiley & Sons, Inc.