An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs

DOI10.1007/978-3-540-79723-4_7zbMath1142.68596OpenAlexW2085170023MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Fast algorithms for max independent set ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3

Cites Work

• Pathwidth of cubic graphs and exact algorithms
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Algorithms and Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs