Exact algorithms for maximum independent set

DOI10.1016/j.ic.2017.06.001zbMath1371.68126arXiv1312.6260OpenAlexW1518653692WikidataQ56335614 ScholiaQ56335614MaRDI QIDQ2013558

Mingyu Xiao, Hiroshi Nagamochi

Publication date: 8 August 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.6260

zbMATH Keywords

graphindependent setexact algorithmmeasure-and-conqueramortized analysisbranch-and-reducepolynomial-space

Mathematics Subject Classification ID

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

Related Items

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ On comparing algorithms for the maximum clique problem ⋮ Exact algorithms for maximum induced matching ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Further improvements for SAT in terms of formula length ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set} ⋮ On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\) ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the complexity of detecting hazards ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Solving vertex cover in polynomial time on hyperbolic random graphs ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Unnamed Item ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Exact exponential algorithms.
• An exact algorithm for maximum independent set in degree-5 graphs
• 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
• Fast algorithms for max independent set
• Vertex Cover: Further Observations and Further Improvements
• Exact Algorithms for Maximum Independent Set
• A Fine-grained Analysis of a Simple Independent Set Algorithm
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
• A measure & conquer approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Finding a Maximum Independent Set
• Unnamed Item
• Unnamed Item
• Unnamed Item