Algorithms for maximum independent sets
From MaRDI portal
Publication:3777476
DOI10.1016/0196-6774(86)90032-5zbMath0637.68080OpenAlexW2073025989WikidataQ55891739 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
Faster exact algorithms for some terminal set problems ⋮ Graph separators: A parameterized view ⋮ Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms ⋮ Improved exact algorithms for MAX-SAT ⋮ Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Solving the maximum clique problem using a tabu search approach ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Refined memorization for vertex cover ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ On Independent Sets and Bicliques in Graphs ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ On CLIQUE Problem for Sparse Graphs of Large Dimension ⋮ 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 ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ A multivariate framework for weighted FPT algorithms ⋮ On comparing algorithms for the maximum clique problem ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Exact algorithms for maximum induced matching ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ On testing monomials in multivariate polynomials ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Complement, Complexity, and Symmetric Representation ⋮ New upper bounds for the problem of maximal satisfiability ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Exact Algorithms for Edge Domination ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Exact algorithms for dominating set ⋮ An approximation algorithm for 3-Colourability ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Fast algorithms for max independent set ⋮ On independent sets and bicliques in graphs ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ 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 ⋮ Nearly exact mining of frequent trees in large networks ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ 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 ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ Open problems around exact algorithms ⋮ Solving connected dominating set faster than \(2^n\) ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Algorithms for dominating clique problems ⋮ Finding a dominating set on bipartite graphs ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ In search of the densest subgraph ⋮ A branch and bound algorithm for the maximum clique problem ⋮ A stronger model of dynamic programming algorithms ⋮ Variable neighborhood search for the maximum clique ⋮ Exact algorithms for maximum independent set ⋮ Efficient algorithms for clique problems ⋮ Improved upper bounds for vertex cover ⋮ On the complexity of \(k\)-SAT ⋮ Iterative compression and exact algorithms ⋮ Iterative Compression and Exact Algorithms ⋮ Components in time-varying graphs ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ On the computational power of DNA ⋮ Layered graphs: applications and algorithms ⋮ Efficiency in exponential time for domination-type problems ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ Auto-G-Computation of Causal Effects on a Network ⋮ Combinatorial properties of Farey graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Faster exact solutions for some NP-hard problems. ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Which problems have strongly exponential complexity? ⋮ The maximum clique problem ⋮ Moderately exponential time algorithms for the maximum induced matching problem
