On the Maximum Independent Set Problem in Subclasses of Planar Graphs | Zendy

Vadim Lozin | Zendy; Martin Milanič | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Maximum Independent Set Problem in Subclasses of Planar Graphs

Author(s) -

Vadim Lozin,

Martin Milanič

Publication year - 2010

Publication title -

journal of graph algorithms and applications

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.387

H-Index - 38

ISSN - 1526-1719

DOI - 10.7155/jgaa.00207

Subject(s) - combinatorics , set (abstract data type) , planar , planar graph , mathematics , chordal graph , outerplanar graph , independent set , maximal independent set , computer science , pathwidth , 1 planar graph , discrete mathematics , graph , line graph , computer graphics (images) , programming language

The maximum independent set problem is known to be NP-hard in the class of planar graphs. In the present paper, we study its complexity in hereditary subclasses of planar graphs. In particular, by combining various techniques, we show that the problem is polynomially solvable in the class of S1,2,k-free planar graphs, generalizing several previously known results. S1,2,k is the graph consisting of three induced paths of lengths 1, 2 and k, with a common initial vertex.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research