Algorithms for maximum independent sets
From MaRDI portal
Publication:3777476
DOI10.1016/0196-6774(86)90032-5zbMath0637.68080WikidataQ55891739 ScholiaQ55891739MaRDI QIDQ3777476
Publication date: 1986
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(86)90032-5
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05-04: Software, source code, etc. for problems pertaining to combinatorics
Related Items
Unnamed Item, On Independent Sets and Bicliques in Graphs, A branch and bound algorithm for the maximum clique problem, On the complexity of \(k\)-SAT, On the computational power of DNA, Algorithms for four variants of the exact satisfiability problem, Variable neighborhood search for the maximum clique, Improved upper bounds for vertex cover, Refined memorization for vertex cover, Isolation concepts for efficiently enumerating dense subgraphs, Strong computational lower bounds via parameterized complexity, The worst-case time complexity for generating all maximal cliques and computational experiments, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, An efficient fixed-parameter algorithm for 3-hitting set, Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs, Solving connected dominating set faster than \(2^n\), On the minimum feedback vertex set problem: Exact and enumeration algorithms, Finding a dominating set on bipartite graphs, Computing branchwidth via efficient triangulations and blocks, Efficient algorithms for clique problems, Efficiency in exponential time for domination-type problems, The maximum clique problem, Which problems have strongly exponential complexity?, Faster exact solutions for some NP-hard problems., Graph separators: A parameterized view, Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms, Improved exact algorithms for MAX-SAT, Iterative compression and exact algorithms, Solving the maximum clique problem using a tabu search approach, An exact algorithm for the minimum dominating clique problem, A note on the complexity of minimum dominating set, Open problems around exact algorithms, Parameterized computation and complexity: a new approach dealing with NP-hardness, A new algorithm for optimal 2-constraint satisfaction and its implications, Exponential Time Complexity of Weighted Counting of Independent Sets, Exact Algorithms for Edge Domination, Iterative Compression and Exact Algorithms
