Maximum Independent Set in graphs of average degree at most three in O(1.08537ⁿ)

DOI10.1007/978-3-642-13562-0_34MaRDI QIDQ3569091zbMATH OpenOpenAlexFDO

Authors Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, 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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

Cited in

(11)

• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• A refined algorithm for maximum independent set in degree-4 graphs
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• On the independence number of graphs with maximum degree 3
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Inclusion/exclusion meets measure and conquer
• Fast algorithms for max independent set
• Parameterized edge dominating set in cubic graphs (extended abstract)
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Parameterized edge dominating set in graphs with degree bounded by 3

This page was built for publication: Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569091)