Fast algorithms for max independent set
From MaRDI portal
Publication:2428670
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
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, 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, 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, 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
- 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
- Unnamed Item
