@techreport{TD:100093, att_abstract={{Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing a single vertex with two others. The second routine can determine in O(m D)$ time (where D is the highest degree in the graph) whether there are two solution vertices than can be replaced by a set of three. We also present a more elaborate heuristic that successfully applies local search to find near-optimum solutions to a wide variety of instances. We test our algorithms on instances from the literature as well as on new ones proposed in this paper. }}, att_authors={mr5626}, att_categories={C_CCF.1, C_CCF.2, C_CCF.7, C_CCF.8}, att_copyright={{Springer}}, att_copyright_notice={{The definitive version was published in Ambient Intelligence Perspectives . {{, 2012-02-25}} }}, att_donotupload={}, att_private={false}, att_projects={}, att_tags={maximum independent set, local search, iterated local search, algorithm engineering}, att_techdoc={true}, att_techdoc_key={TD:100093}, att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100093_DS1_2010-06-29T17:57:15.808Z.pdf}, author={Mauricio Resende and Diego V. Andrade, Google and Renato F. Werneck}, institution={{Journal of Heuristics}}, month={February}, title={{Fast local search for the maximum independent set problem}}, year=2012, }