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)

• 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
• Interior and exterior functions of Boolean functions
• A general method for generating all maximal independent sets of a graph
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions
• Computing and listing \(st\)-paths in public transportation networks
• Generating 3-vertex connected spanning subgraphs
• Generate all maximal independent sets in permutation graphs
• In search of the densest subgraph
• Listing minimal edge-covers of intersecting families with applications to connectivity problems
• On the Complexity of Computing Generators of Closed Sets
• An incremental algorithm for computing ranked full disjunctions
• Listing closed sets of strongly accessible set systems with applications to data mining
• An inequality for polymatroid functions and its applications.
• Enumerating maximal consistent closed sets in closure systems
• Maximum weight edge-constrained matchings
• On the complexity of the dualization problem
• Maximal independent sets in clique-free graphs
• Closure-based constraints in formal concept analysis
• Combinatorial optimization in system configuration design
• Computing maximal cliques in link streams
• Probabilistic and exact frequent subtree mining in graphs beyond forests
• Minimal winning coalitions and orders of criticality
• Maximal induced matchings in triangle-free graphs
• Resolution based algorithms for the transversal hypergraph generation problem
• Efficiently enumerating minimal triangulations
• Efficient reasoning for inconsistent Horn formulae
• Efficient enumeration of maximal induced bicliques
• Iterative Compression and Exact Algorithms
• Parameterized random complexity
• Title not available (Why is that?)
• Complexity of DNF minimization and isomorphism testing for monotone formulas
• Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
• Asymptotically optimal dualization algorithms
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• 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

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)