Paper ID: 6525
DCS Tech Report Number: TR199733
On the 2maximal independence number of a graph
Manlove,D.F.
Publication Type:
Tech Report (internal)
Appeared in:
DCS Tech Report
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 1997
Abstract:
An independent set S of a graph G=(V,E) is kmaximal (k>=1) if, for all subsets A of S (where A<=k1), and all subsets B of V\S (where B=A+1), (S\A)\cup B is nonindependent. Halldórsson (Approximating discrete collections via local improvements, in Proceedings of the 6th Annual ACMSIAM Symposium on Discrete Algorithms, San Francisco, pages 160169. ACMSIAM, 1995) uses kmaximal independent sets as a means of approximating maximum independent sets in certain graph classes. Here we study the parameter \beta_{0,2}^(T), the smallest order of a 2maximal independent set of a graph G, from an algorithmic point of view. We obtain a linear time and space algorithm for computing \beta_{0,2}^(T) for a tree T and also for constructing a minimum 2maximal independent set of T. We also show that the decision problem related to computing \beta_{0,2}^(T) is NPcomplete for planar graphs of maximum degree three.
