Madhavan, CEV (1984) Approximation algorithm for maximum independent set in planar traingle-free graphs. In: Lecture Notes in Computer Science, 181 . pp. 381-392.Full text not available from this repository. (Request a copy)
The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.
|Item Type:||Journal Article|
|Additional Information:||Copyright of this article belongs to Springer.|
|Department/Centre:||Division of Electrical Sciences > Computer Science & Automation (Formerly, School of Automation)|
|Date Deposited:||14 Aug 2009 06:33|
|Last Modified:||14 Aug 2009 06:33|
Actions (login required)