Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
From MaRDI portal
Publication:3890128
DOI10.1137/0209042zbMath0445.68054OpenAlexW2093776691WikidataQ59409900 ScholiaQ59409900MaRDI QIDQ3890128
Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, Eugene L. Lawler
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://research.tue.nl/nl/publications/a4b8731e-7a3f-4f84-8aa1-1c2f076cbc5a
knapsack problemset packingcliquesatisfiabilityindependence systemNP-hardnesspolynomial-time algorithmsmatroid intersectionfacet generationcomplete k-partite subgraphlexicography testmaximality test
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)
Related Items (88)
On the completability of incomplete orthogonal Latin rectangles ⋮ Generating all maximal independent sets on trees in lexicographic order ⋮ Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Enumeration of support-closed subsets in confluent systems ⋮ Polynomial-time algorithms for regular set-covering and threshold synthesis ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Listing closed sets of strongly accessible set systems with applications to data mining ⋮ On enumerating all minimal solutions of feedback problems ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ 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 ⋮ ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS ⋮ On generating all maximal independent sets ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ The worst-case time complexity for generating all maximal cliques and computational experiments ⋮ Interior and exterior functions of Boolean functions ⋮ Maximal independent sets in clique-free graphs ⋮ Horn functions and submodular Boolean functions ⋮ On vertex independence number of uniform hypergraphs ⋮ On Dualization over Distributive Lattices ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Output-size sensitiveness of OBDD construction through maximal independent set problem ⋮ Exact Algorithms for Edge Domination ⋮ Polynomial-delay enumeration algorithms in set systems ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Cograph generation with linear delay ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ A renewal approach to configurational entropy in one dimension ⋮ On the complexity of enumerating pseudo-intents ⋮ Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements ⋮ On computing large temporal (unilateral) connected components ⋮ Exact algorithms for edge domination ⋮ Invited talks ⋮ An inequality for polymatroid functions and its applications. ⋮ Factor models on locally tree-like graphs ⋮ A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically ⋮ 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 ⋮ Detecting anomaly collections using extreme feature ranks ⋮ Inner-core and outer-core functions of partially defined Boolean functions ⋮ Counting Minimal Dominating Sets ⋮ Unranking of small combinations from large sets ⋮ Generating cut conjunctions in graphs and related problems ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Solving the feedback vertex set problem on undirected graphs ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Self-duality of bounded monotone Boolean functions and related problems ⋮ Efficiently enumerating minimal triangulations ⋮ Maximal strongly connected cliques in directed graphs: algorithms and bounds ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ On the generation of circuits and minimal forbidden sets ⋮ Consensus algorithms for the generation of all maximal bicliques ⋮ Generating bicliques of a graph in lexicographic order ⋮ Generating dual-bounded hypergraphs ⋮ Incremental delay enumeration: space and time ⋮ A fast discovery algorithm for large common connected induced subgraphs ⋮ Unnamed Item ⋮ Hypergraph Horn functions ⋮ Decision lists and related Boolean functions ⋮ Local multiple alignment via subgraph enumeration ⋮ On the computation of fixed points in Boolean networks ⋮ Generating 3-vertex connected spanning subgraphs ⋮ On the generation of bicliques of a graph ⋮ Listing minimal edge-covers of intersecting families with applications to connectivity problems ⋮ Interesting pattern mining in multi-relational data ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Minimum partition of an independence system into independent sets ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Generating all vertices of a polyhedron is hard ⋮ Unnamed Item ⋮ On the complexity of solution extension of optimization problems ⋮ Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ A new backtracking algorithm for generating the family of maximal independent sets of a graph ⋮ A framework for the complexity of high-multiplicity scheduling problems ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ The maximum clique problem ⋮ Version spaces and the consistency problem ⋮ Enumeration of maximal common subsequences between two strings
This page was built for publication: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
