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

DOI10.1109/TC.1986.1676847zbMath0606.68062OpenAlexW1971756951WikidataQ56210422 ScholiaQ56210422MaRDI QIDQ3745299

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

NP-completenesscase analysisdeterministic upper bound

Mathematics Subject Classification ID

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.