<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>6525</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>1997</YEAR><TITLE>On the 2-maximal independence number of a graph</TITLE><PLACE_PUBLISHED>DCS Tech Report</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-1997-33</ISBN><LABEL>Manlove:1997:6525</LABEL><ABSTRACT>An independent set S of a graph G=(V,E) is k-maximal (k>=1) if, for all subsets A of S (where |A|<=k-1), and all subsets B of V\S (where |B|=|A|+1), (S\A)\cup B is non-independent. Halldórsson (Approximating discrete collections via local improvements, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pages 160-169. ACM-SIAM, 1995) uses k-maximal 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 2-maximal 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 2-maximal independent set of T. We also show that the decision problem related to computing \beta_{0,2}^-(T) is NP-complete for planar graphs of maximum degree three.</ABSTRACT></RECORD></RECORDS></XML>