Exact algorithms for maximum independent set
From MaRDI portal
Publication:2013558
DOI10.1016/J.IC.2017.06.001zbMATH Open1371.68126DBLPjournals/iandc/XiaoN17arXiv1312.6260OpenAlexW1518653692WikidataQ56335614 ScholiaQ56335614MaRDI QIDQ2013558FDOQ2013558
Authors: Mingyu Xiao, Hiroshi Nagamochi 
Publication date: 8 August 2017
Published in: Information and Computation (Search for Journal in Brave)
Abstract: We show that the maximum independent set problem (MIS) on an -vertex graph can be solved in time and polynomial space, which even is faster than Robson's -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of and , respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analyses on the structure of bounded-degree graphs.
Full work available at URL: https://arxiv.org/abs/1312.6260
Recommendations
graphexact algorithmmeasure-and-conquerindependent setamortized analysisbranch-and-reducepolynomial-space
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- A refined algorithm for maximum independent set in degree-4 graphs
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- A measure & conquer approach for the analysis of exact algorithms
- Title not available (Why is that?)
- Exact exponential algorithms.
- Title not available (Why is that?)
- Fast algorithms for max independent set
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Algorithms for maximum independent sets
- Vertex cover: Further observations and further improvements
- A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- A fine-grained analysis of a simple independent set algorithm
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Finding a Maximum Independent Set
- Title not available (Why is that?)
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Exact Algorithms for Maximum Independent Set
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
- An exact algorithm for maximum independent set in degree-5 graphs
Cited In (43)
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Conflict free version of covering problems on graphs: classical and parameterized
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
- Title not available (Why is that?)
- On kernels for \(d\)-path vertex cover
- Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
- A bisection approach to subcubic maximum induced matching
- Exact Solution Algorithms for the Chordless Cycle Problem
- On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
- Faster exponential-time algorithms for approximately counting independent sets
- Algorithms for maximum independent sets
- Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Exact Algorithms for Maximum Independent Set
- An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
- Exact algorithms for maximum induced matching
- A bottom-up method and fast algorithms for Max Independent Set
- \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
- A note on the fine-grained complexity of MIS on regular graphs
- Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
- Title not available (Why is that?)
- Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Reinforcement learning for combinatorial optimization: a survey
- An exact algorithm for maximum independent set in degree-5 graphs
- Minimum number of maximal dissociation sets in trees
- A fine-grained analysis of a simple independent set algorithm
- On comparing algorithms for the maximum clique problem
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
- Targeted Branching for the Maximum Independent Set Problem
- Exact algorithms for counting 3-colorings of graphs
- Generating Faster Algorithms for d-Path Vertex Cover
- Turán’s Theorem Through Algorithmic Lens
- An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
- Approximation algorithms for maximum independent set of pseudo-disks
- Solving vertex cover in polynomial time on hyperbolic random graphs
- On the complexity of detecting hazards
- Moderate exponential-time algorithms for scheduling problems
- Further improvements for SAT in terms of formula length
This page was built for publication: Exact algorithms for maximum independent set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013558)
