An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
From MaRDI portal
Publication:3503578
DOI10.1007/978-3-540-79723-4_7zbMath1142.68596MaRDI QIDQ3503578
Bruno Escoffier, Nicolas Bourgeois, Vangelis Th. Paschos
Publication date: 5 June 2008
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79723-4_7
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3, Fast algorithms for max independent set
Cites Work