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
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, 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
