An O(20.304n) Algorithm for Solving Maximum Independent Set Problem

DOI10.1109/TC.1986.1676847MaRDI QIDQ3745299zbMATH OpenOpenAlexWikidataFDO

Authors Tang Jian

Publication date 1986

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tc.1986.1676847

zbMATH Keywords

case analysisdeterministic upper boundNP-completeness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms for maximum independent sets
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Exact Algorithms for Maximum Independent Set
• Exact algorithms for maximum independent set
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)

Cited in

(26)

• A faster version of the ASG algorithm
• On comparing algorithms for the maximum clique problem
• A refined algorithm for maximum independent set in degree-4 graphs
• Faster exact solutions for some NP-hard problems.
• Exact algorithms for maximum independent set
• Extending the MAX algorithm for maximum independent set
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• A note on the complexity of minimum dominating set
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• On the independent set problem in random graphs
• Exact Algorithms for Maximum Independent Set
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Maximum independent set for intervals by divide and conquer with pruning
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Algorithms for maximum independent sets
• scientific article; zbMATH DE number 2079379 (Why is no real title available?)
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Fast local search for the maximum independent set problem
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• On the complexity of k-SAT
• Algorithms for four variants of the exact satisfiability problem
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Strong computational lower bounds via parameterized complexity
• An efficient fixed-parameter algorithm for 3-hitting set
• An exact algorithm for maximum independent set in degree-5 graphs
• Computing branchwidth via efficient triangulations and blocks

This page was built for publication: An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3745299)