Fast algorithms for max independent set
From MaRDI portal
Publication:2428670
DOI10.1007/s00453-010-9460-7zbMath1241.68087OpenAlexW2044104853MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (26)
MP or not MP: that is the question ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ On bipartization of cubic graphs by removal of an independent set ⋮ Partition into triangles on bounded degree graphs ⋮ Finding near-optimal independent sets at scale ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs ⋮ Inclusion/exclusion meets measure and conquer ⋮ Algorithms for dominating clique problems ⋮ Exact algorithms for maximum independent set ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ An improved exact algorithm for undirected feedback vertex set
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Fast algorithms for max independent set
