On generating all maximal independent sets

DOI10.1016/0020-0190(88)90065-8zbMATH Open0654.68086OpenAlexW2007940874WikidataQ56210424 ScholiaQ56210424MaRDI QIDQ1108809FDOQ1108809

Authors: D. S. Johnson, Mihalis Yannakakis, Christos 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

Recommendations

• A generalization of maximal independent sets
• On the maximum number of maximum independent sets
• A general method for generating all maximal independent sets of a graph
• scientific article; zbMATH DE number 637355
• Generating all maximal independent sets on trees in lexicographic order
• Maximizing the number of independent sets of a fixed size
• Publication:4486258
• Critical and maximum independent sets revisited
• Maximum independent sets near the upper bound
• Publication:4864968

zbMATH Keywords

enumerationlexicographic orderNP-completeindependent sets

Mathematics Subject Classification ID

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

Cites Work

• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• How to assign votes in a distributed system
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Title not available (Why is that?)
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations

Cited In (only showing first 100 items - show all)

• Spanned patterns for the logical analysis of data
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• A framework for the complexity of high-multiplicity scheduling problems
• On Independent Sets and Bicliques in Graphs
• The maximum clique problem
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Lower bounds for three algorithms for transversal hypergraph generation
• Generating all maximal models of a Boolean expression
• Listing graphs that satisfy first-order sentences
• Enumerating homomorphisms
• Finding kernels or solving SAT
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• Enumeration of the perfect sequences of a chordal graph
• On vertex independence number of uniform hypergraphs
• Generating all vertices of a polyhedron is hard
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Parameterized edge dominating set in cubic graphs (extended abstract)
• Probably approximately correct learning of Horn envelopes from queries
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• On two techniques of combining branching and treewidth
• Decision lists and related Boolean functions
• Generating bicliques of a graph in lexicographic order
• All maximal independent sets and dynamic dominance for sparse graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• Consensus algorithms for the generation of all maximal bicliques
• On the generation of circuits and minimal forbidden sets
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• On the complexity of hard enumeration problems
• Constraints on the number of maximal independent sets in graphs
• New parameterized algorithms for the edge dominating set problem
• Scheduling modular projects on a bottleneck resource
• Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data
• Multiplicity and complexity issues in contemporary production scheduling
• Decompositions of positive self-dual Boolean functions
• Fuzzy relational equations with min-biimplication composition
• Horn functions and submodular Boolean functions
• Minimum self-dual decompositions of positive dual-minor Boolean functions
• Counting truth assignments of formulas of bounded tree-width or clique-width
• An exact algorithm for the minimum dominating clique problem
• Generating cut conjunctions in graphs and related problems
• A refined exact algorithm for edge dominating set
• An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem
• Exact Algorithms for Edge Domination
• Generating dual-bounded hypergraphs
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Computational aspects of monotone dualization: a brief survey
• Graph theoretical structures in logic programs and default theories
• Complexity of learning in concept lattices from positive and negative examples
• NP-completeness: a retrospective
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Parallel algorithm for computing fixpoints of Galois connections
• Comparing performance of algorithms for generating concept lattices
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Graphs with the second largest number of maximal independent sets
• On enumerating all minimal solutions of feedback problems
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• Counting and enumerating preferred database repairs
• Enumeration of minimal dominating sets and variants
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Solving the maximum clique problem using a tabu search approach
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• Enumeration aspects of maximal cliques and bicliques
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• Double Horn functions
• Completing causal networks by meta-level abduction
• On the complexity of enumerating pseudo-intents
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Maximal independent sets in caterpillar graphs
• Exact algorithms for edge domination
• Fast maximal cliques enumeration in sparse graphs
• Version spaces and the consistency problem
• Iterative compression and exact algorithms
• Forms of representation for simple games: sizes, conversions and equivalences
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• Parameterized edge dominating set in graphs with degree bounded by 3
• On maximal chain subgraphs and covers of bipartite graphs
• The number of maximal independent sets in connected triangle-free graphs
• On generating all solutions of generalized satisfiability problems
• Counting and enumeration complexity with application to multicriteria scheduling
• Recognition and dualization of disguised bidual Horn functions.
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Incremental delay enumeration: space and time
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• Satisfiability of mixed Horn formulas
• Polynomial-delay construction of irreducible coverings of a Boolean matrix
• Querying disjunctive databases through nonmonotonic logics
• Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
• The Helly property and satisfiability of Boolean formulas defined on set families
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Interior and exterior functions of positive Boolean functions.
• Bidual Horn functions and extensions
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Theoretical underpinnings for maximal clique enumeration on perturbed graphs
• Generating all maximal independent sets on trees in lexicographic order
• Loopless Gray code enumeration and the Tower of Bucharest
• Efficient frequent connected subgraph mining in graphs of bounded tree-width
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108809)