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 (only showing first 100 items - show all)

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

This page was built for publication: On generating all maximal independent sets