An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
From MaRDI portal
Publication:3745299
DOI10.1109/TC.1986.1676847zbMath0606.68062OpenAlexW1971756951WikidataQ56210422 ScholiaQ56210422MaRDI QIDQ3745299
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Strong computational lower bounds via parameterized complexity ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ On comparing algorithms for the maximum clique problem ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ A note on the complexity of minimum dominating set ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Exact algorithms for maximum independent set ⋮ On the complexity of \(k\)-SAT ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ On the independent set problem in random graphs ⋮ Faster exact solutions for some NP-hard problems.
