Back to Search
Start Over
An exact algorithm for maximum independent set in degree-5 graphs.
- Source :
-
Discrete Applied Mathematics . Jan2016, Vol. 199, p137-155. 19p. - Publication Year :
- 2016
-
Abstract
- The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.173 6 n n O ( 1 ) -time exact algorithm for the maximum independent set problem in an n -vertex graph with degree bounded by 5 , improving the previous running time bound of 1.189 5 n n O ( 1 ) . In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 199
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 111486070
- Full Text :
- https://doi.org/10.1016/j.dam.2014.07.009