@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,
}