An exact algorithm for maximum independent set in degree-5 graphs

التفاصيل البيبلوغرافية
العنوان: An exact algorithm for maximum independent set in degree-5 graphs
المؤلفون: Mingyu Xiao, Hiroshi Nagamochi
المصدر: Discrete Applied Mathematics. 199:137-155
بيانات النشر: Elsevier BV, 2016.
سنة النشر: 2016
مصطلحات موضوعية: Discrete mathematics, Matching (graph theory), Applied Mathematics, Vertex cover, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, Dominating set, Independent set, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, 020201 artificial intelligence & image processing, Feedback vertex set, Maximal independent set, Split graph, Hopcroft–Karp algorithm, Mathematics
الوصف: 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.
تدمد: 0166-218X
DOI: 10.1016/j.dam.2014.07.009
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_________::09153b9bfcee71501ec0f36f58b59771
https://doi.org/10.1016/j.dam.2014.07.009
Rights: OPEN
رقم الانضمام: edsair.doi...........09153b9bfcee71501ec0f36f58b59771
قاعدة البيانات: OpenAIRE
الوصف
تدمد:0166218X
DOI:10.1016/j.dam.2014.07.009