Fast algorithms for max independent set

DOI10.1007/s00453-010-9460-7zbMath1241.68087MaRDI QIDQ2428670

Johan M. M. van Rooij, Vangelis Th. Paschos, Bruno Escoffier, Nicolas Bourgeois

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9460-7

zbMATH Keywords

exact algorithms; bottom-up method; max independent set

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†, MP or not MP: that is the question, On bipartization of cubic graphs by removal of an independent set, Solving min ones 2-SAT as fast as vertex cover, An exact exponential time algorithm for counting bipartite cliques, Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs, An exact algorithm for maximum independent set in degree-5 graphs, Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover, A refined algorithm for maximum independent set in degree-4 graphs, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Algorithms for dominating clique problems, Exact algorithms for maximum independent set, A note on the fine-grained complexity of MIS on regular graphs, Exact algorithms for counting 3-colorings of graphs, Inclusion/exclusion meets measure and conquer, An improved exact algorithm for undirected feedback vertex set, Partition into triangles on bounded degree graphs, Finding near-optimal independent sets at scale, Computing the differential of a graph: hardness, approximability and exact algorithms, Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract), On the Power of Simple Reductions for the Maximum Independent Set Problem, An Improved Exact Algorithm for Undirected Feedback Vertex Set, Moderately exponential time and fixed parameter approximation algorithms, Large Induced Subgraphs via Triangulations and CMSO

Cites Work

• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• On two techniques of combining branching and treewidth
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Pathwidth of cubic graphs and exact algorithms
• Counting models for 2SAT and 3SAT formulae
• A Fine-grained Analysis of a Simple Independent Set Algorithm
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$
• A new approach to proving upper bounds for MAX-2-SAT
• Algorithms for maximum independent sets
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item