Finding a Maximum Independent Set
From MaRDI portal
Publication:4133117
DOI10.1137/0206038zbMath0357.68035OpenAlexW2097844290WikidataQ56210440 ScholiaQ56210440MaRDI QIDQ4133117
Anthony E. Trojanowski, Robert Endre Tarjan
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0206038
Related Items (81)
Determining the number of internal stability of a graph ⋮ An algorithm for the maximum internally stable set in a weighted graph ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Solving the maximum clique problem using a tabu search approach ⋮ Average polynomial time complexity of some NP-complete problems ⋮ Unsupervised feature selection for efficient exploration of high dimensional data ⋮ Strong computational lower bounds via parameterized complexity ⋮ Treewidth computation and extremal combinatorics ⋮ The worst-case time complexity for generating all maximal cliques and computational experiments ⋮ Discrete dynamical system approaches for Boolean polynomial optimization ⋮ On finding a minimum dominating set in a tournament ⋮ An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments ⋮ Finding near-optimal independent sets at scale ⋮ A global optimization approach for solving the maximum clique problem ⋮ A faster algorithm for maximum independent set on interval filament graphs ⋮ On comparing algorithms for the maximum clique problem ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ An algorithm for finding a maximum weighted independent set in an arbitrary graph ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ Branch-and-bound techniques for the maximum planar subgraph problem∗ ⋮ Cover by disjoint cliques cuts for the knapsack problem with conflicting items ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ On vertex independence number of uniform hypergraphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Exact Algorithms for Edge Domination ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Exact algorithms for dominating set ⋮ An approximation algorithm for 3-Colourability ⋮ Analysis of an iterated local search algorithm for vertex cover in sparse random graphs ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Exact algorithms for edge domination ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ An exact algorithm for the maximum clique problem ⋮ Unnamed Item ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs ⋮ A note on the complexity of minimum dominating set ⋮ Path Contraction Faster than $2^n$ ⋮ Genetic algorithmic approach to find the maximum weight independent set of a graph ⋮ Open problems around exact algorithms ⋮ Hard graphs for the maximum clique problem ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Finding a dominating set on bipartite graphs ⋮ A branch and bound algorithm for the maximum clique problem ⋮ On the probable behaviour of some algorithms for finding the stability number of a graph ⋮ Exact algorithms for maximum independent set ⋮ On the complexity of \(k\)-SAT ⋮ Iterative compression and exact algorithms ⋮ On the computational hardness based on linear fpt-reductions ⋮ Iterative Compression and Exact Algorithms ⋮ New models and algorithms for RNA pseudoknot order assignment ⋮ Components in time-varying graphs ⋮ A differentiable approach to the maximum independent set problem using dataless neural networks ⋮ Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs ⋮ On the computational power of DNA ⋮ Layered graphs: applications and algorithms ⋮ Solving NP-Complete Problems with Quantum Search ⋮ An algorithm for finding a maximum clique in a graph ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ Path Contraction Faster Than 2^n ⋮ Improved simulation of nondeterministic Turing machines ⋮ Fuzzy graphs and networks repairs ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ Homogeneous genetic algorithms ⋮ Enumerating all connected maximal common subgraphs in two graphs ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Faster exact solutions for some NP-hard problems. ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Solving NP-hard problems in 'almost trees': vertex cover ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ Which problems have strongly exponential complexity? ⋮ The maximum clique problem
This page was built for publication: Finding a Maximum Independent Set
