On generating all maximal independent sets

DOI10.1016/0020-0190(88)90065-8zbMath0654.68086OpenAlexW2007940874WikidataQ56210424 ScholiaQ56210424MaRDI QIDQ1108809

Mihalis Yannakakis, David S. Johnson, Christos H. Papadimitriou

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90065-8

zbMATH Keywords

lexicographic order enumeration NP-complete independent sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Fixed points in conjunctive networks and maximal independent sets in graph contractions, Solving the maximum clique problem using a tabu search approach, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Enumeration of support-closed subsets in confluent systems, Proximity Search for Maximal Subgraph Enumeration, Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems, On the fixed-parameter tractability of the equivalence test of monotone normal forms, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs, On Independent Sets and Bicliques in Graphs, Path Problems in Complex Networks, Constraints on the number of maximal independent sets in graphs, Paradigms for parameterized enumeration, Solving a constrained economic lot size problem by ranking efficient production policies, NP-completeness: A retrospective, Enumerating teams in first-order team logics, Efficiently Listing Bounded Length st-Paths, LoCo—A Logic for Configuration Problems, Enumeration of irredundant forests, Maximal independent sets in clique-free graphs, Polynomial-delay and polynomial-space enumeration of large maximal matchings, On Dualization over Distributive Lattices, Lattice point of view for argumentation framework, Systematic categorization and evaluation of CbO-based algorithms in FCA, The Minimal Hitting Set Generation Problem: Algorithms and Computation, The smallest hard trees, Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions, Exact Algorithms for Edge Domination, On the preferred extensions of argumentation frameworks: bijections with naive sets, Counting and enumerating preferred database repairs, Probabilistic and exact frequent subtree mining in graphs beyond forests, Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation, One approach to decoding monotone logical function, Parallel algorithm for computing fixpoints of Galois connections, Unnamed Item, Closure-based constraints in formal concept analysis, Generating clause sequences of a CNF formula, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Listing Maximal Subgraphs Satisfying Strongly Accessible Properties, An exact algorithm for the minimum dominating clique problem, Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Parameterized Edge Dominating Set in Cubic Graphs, Listing Maximal Independent Sets with Minimal Space and Bounded Delay, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, On the Parameterized Complexity of Clique Elimination Distance, Counting truth assignments of formulas of bounded tree-width or clique-width, A Structure Theorem for Rooted Binary Phylogenetic Networks and Its Implications for Tree-Based Networks, Maximum weight edge-constrained matchings, On generating all solutions of generalized satisfiability problems, On the difference of Horn theories, The Weight in Enumeration, Multiplicity and complexity issues in contemporary production scheduling, Computing and Listing st-Paths in Public Transportation Networks, Spanned patterns for the logical analysis of data, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Unnamed Item, Generating dual-bounded hypergraphs, Iterative compression and exact algorithms, Comparing performance of algorithms for generating concept lattices, Incremental delay enumeration: space and time, A complexity theory for hard enumeration problems, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay, Iterative Compression and Exact Algorithms, Unnamed Item, On the Complexity of Computing Generators of Closed Sets, Decision lists and related Boolean functions, On the logical analysis of partially ordered data in the supervised classification problem, Local multiple alignment via subgraph enumeration, Parameterized Enumeration for Modification Problems, Probably approximately correct learning of Horn envelopes from queries, On the generation of bicliques of a graph, Design and results of the second international competition on computational models of argumentation, Maximal Induced Matchings in Triangle-Free Graphs, How we designed winning algorithms for abstract argumentation and which insight we attained, Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games, Parameterized complexity of conflict-free set cover, A new approximate cluster deletion algorithm for diamond-free graphs, Unnamed Item, Parallel Algorithm for Enumerating Maximal Cliques in Complex Network, Dualization in lattices given by implicational bases, Counting and enumeration complexity with application to multicriteria scheduling, Enumeration of Minimal Dominating Sets and Variants, On Maximal Chain Subgraphs and Covers of Bipartite Graphs, Randomized generation of error control codes with automata and transducers, Generating all vertices of a polyhedron is hard, Resolution based algorithms for the transversal hypergraph generation problem, Mine ’Em All: A Note on Mining All Graphs, Unnamed Item, Efficient Reasoning for Inconsistent Horn Formulae, Finding maximal independent elements of products of partial orders (the case of chains), On the complexity of the dualization problem, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Transducing Markov sequences, Unnamed Item, On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm, A framework for the complexity of high-multiplicity scheduling problems, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Asymptotically optimal dualization algorithms, Enumerating maximal consistent closed sets in closure systems, Output-size sensitiveness of OBDD construction through maximal independent set problem, Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks, Mining ℰℒ⊥ Bases with Adaptable Role Depth, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements, Shortest distances as enumeration problem, On the hardness of inclusion-wise minimal separators enumeration, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Generating all maximal independent sets on trees in lexicographic order, Dual-bounded generating problems: Weighted transversals of a hypergraph, Complexity of learning in concept lattices from positive and negative examples, Loopless Gray code enumeration and the Tower of Bucharest, Listing graphs that satisfy first-order sentences, Generating all maximal models of a Boolean expression, Computing and listing \(st\)-paths in public transportation networks, Blocker size via matching minors, Decompositions of positive self-dual Boolean functions, Listing closed sets of strongly accessible set systems with applications to data mining, On enumerating all minimal solutions of feedback problems, Querying disjunctive databases through nonmonotonic logics, Efficient enumeration of graph orientations with sources, Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph, Completing causal networks by meta-level abduction, Interior and exterior functions of Boolean functions, Short rational generating functions for solving some families of fuzzy integer programming problems, An incremental algorithm for computing ranked full disjunctions, Enumeration and maximum number of minimal connected vertex covers in graphs, On enumerating monomials and other combinatorial structures by polynomial interpolation, Fuzzy relational equations with min-biimplication composition, Parameterized edge dominating set in graphs with degree bounded by 3, Understanding the complexity of axiom pinpointing in lightweight description logics, New parameterized algorithms for the edge dominating set problem, Horn functions and submodular Boolean functions, Scheduling modular projects on a bottleneck resource, On vertex independence number of uniform hypergraphs, Enumerating minimal dominating sets in chordal bipartite graphs, Computing maximal cliques in link streams, Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy., Finding kernels or solving SAT, Enumerating homomorphisms, Forms of representation for simple games: sizes, conversions and equivalences, Exact algorithms for \(L(2,1)\)-labeling of graphs, On the complexity of enumerating pseudo-intents, Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data, Exact algorithms for edge domination, Interior and exterior functions of positive Boolean functions., Parameterized random complexity, An inequality for polymatroid functions and its applications., Fast maximal cliques enumeration in sparse graphs, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions, Bidual Horn functions and extensions, Minimum self-dual decompositions of positive dual-minor Boolean functions, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, Inner-core and outer-core functions of partially defined Boolean functions, Generating cut conjunctions in graphs and related problems, A refined exact algorithm for edge dominating set, Dualization problem over the product of chains: asymptotic estimates for the number of solutions, A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs, Complexity of DNF minimization and isomorphism testing for monotone formulas, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Graph theoretical structures in logic programs and default theories, A new decomposition technique for maximal clique enumeration for sparse graphs, Computational aspects of monotone dualization: a brief survey, On the complexity of monotone dualization and generating minimal hypergraph transversals, On detecting maximal quasi antagonistic communities in signed graphs, Efficiently enumerating minimal triangulations, Efficient enumeration of maximal induced bicliques, Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, Polynomial-delay construction of irreducible coverings of a Boolean matrix, Algorithms for dominating clique problems, The Helly property and satisfiability of Boolean formulas defined on set families, In search of the densest subgraph, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Counting substrate cycles in topologically restricted metabolic networks, On the generation of circuits and minimal forbidden sets, Theoretical underpinnings for maximal clique enumeration on perturbed graphs, Consensus algorithms for the generation of all maximal bicliques, Enumeration of the perfect sequences of a chordal graph, Generating bicliques of a graph in lexicographic order, Efficient frequent connected subgraph mining in graphs of bounded tree-width, On the dualization in distributive lattices and related problems, Translating between the representations of a ranked convex geometry, Satisfiability of mixed Horn formulas, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Generating 3-vertex connected spanning subgraphs, Graphs with the second largest number of maximal independent sets, Listing minimal edge-covers of intersecting families with applications to connectivity problems, An improved upper bound on maximal clique listing via rectangular fast matrix multiplication, STABULUS: A technique for finding stable sets in large graphs with tabu search, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, On two techniques of combining branching and treewidth, Double Horn functions, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Combinatorial optimization in system configuration design, Enumeration aspects of maximal cliques and bicliques, Lower bounds for three algorithms for transversal hypergraph generation, Maximal independent sets in caterpillar graphs, The number of maximal independent sets in connected triangle-free graphs, An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem, Minimal winning coalitions and orders of criticality, Recognition and dualization of disguised bidual Horn functions., Monotone Boolean dualization is in co-NP\([\log^{2}n\).], Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms, The maximum clique problem, Version spaces and the consistency problem

Cites Work