Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$
From MaRDI portal
Publication:3569091
DOI10.1007/978-3-642-13562-0_34zbMath1284.68290MaRDI QIDQ3569091
Bruno Escoffier, Vangelis Th. Paschos, Nicolas Bourgeois, Johan M. M. van Rooij
Publication date: 17 June 2010
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-13562-0_34
68Q25: Analysis of algorithms and problem complexity
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Parameterized edge dominating set in graphs with degree bounded by 3, A refined algorithm for maximum independent set in degree-4 graphs, Inclusion/exclusion meets measure and conquer, Fast algorithms for max independent set, Parameterized Edge Dominating Set in Cubic Graphs