Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Listing minimal edge-covers of intersecting families with applications to connectivity problems
- On the fractional chromatic number of monotone self-dual Boolean functions
- Minimum partition of an independence system into independent sets
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- On generating all maximal independent sets
- A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
- The maximum clique problem
- Generating all maximal independent sets on trees in lexicographic order
- On enumerating all minimal solutions of feedback problems
- Horn functions and submodular Boolean functions
- An inequality for polymatroid functions and its applications.
- Cograph generation with linear delay
- Detecting anomaly collections using extreme feature ranks
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- On the generation of circuits and minimal forbidden sets
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- Dual-bounded generating problems: Weighted transversals of a hypergraph
- Interior and exterior functions of Boolean functions
- Exact algorithms for edge domination
- Inner-core and outer-core functions of partially defined Boolean functions
- Solving the feedback vertex set problem on undirected graphs
- Efficiently enumerating minimal triangulations
- Maximal strongly connected cliques in directed graphs: algorithms and bounds
- Efficient enumeration of dominating sets for sparse graphs
- On the complexity of solution extension of optimization problems
- Enumeration of maximal common subsequences between two strings
- Enumeration of support-closed subsets in confluent systems
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Incremental delay enumeration: space and time
- A fast discovery algorithm for large common connected induced subgraphs
- 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
- Factor models on locally tree-like graphs
- On enumerating minimal dicuts and strongly connected subgraphs
- On the computation of fixed points in Boolean networks
- A framework for the complexity of high-multiplicity scheduling problems
- On the completability of incomplete orthogonal Latin rectangles
- Maximal independent sets in clique-free graphs
- Invited talks
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
- Counting minimal dominating sets
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- Exact Algorithms for Edge Domination
- On vertex independence number of uniform hypergraphs
- Generating dual-bounded hypergraphs
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Unranking of small combinations from large sets
- ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- Proximity Search for Maximal Subgraph Enumeration
- Efficient enumeration of dominating sets for sparse graphs
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
- Multiplicity and complexity issues in contemporary production scheduling
- Generating bicliques of a graph in lexicographic order
- scientific article; zbMATH DE number 2230256 (Why is no real title available?)
- On the generation of bicliques of a graph
- Generating all vertices of a polyhedron is hard
- Decision lists and related Boolean functions
- Local multiple alignment via subgraph enumeration
- 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
- Polynomial-delay enumeration algorithms in set systems
- Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
- A renewal approach to configurational entropy in one dimension
- Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
- On computing large temporal (unilateral) connected components
- On the complexity of enumerating pseudo-intents
- Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
- Hypergraph Horn functions
- Polynomial-delay enumeration of maximal common subsequences
- On computing large temporal (unilateral) connected components
- Constrained motion planning and multi-agent path finding on directed graphs
- Generating minimal redundant and maximal irredundant subhypergraphs
- Output-sensitive complexity of multi-objective integer network flow problems
- Listing maximal H-free subgraphs
- Conformal hypergraphs: duality and implications for the upper clique transversal problem
- Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond
- A linear delay algorithm in SD set system and its application to subgraph enumeration
- Output-sensitive enumeration of maximal cliques in temporal graphs
- Characterizing traces of processes defined by precedence and response constraints: an order theory approach
- CPAFT: a consistent parallel advancing front technique for unstructured triangular/tetrahedral mesh generation
- Consensus algorithms for the generation of all maximal bicliques
- From amortized to worst case delay in enumeration algorithms
- Interesting pattern mining in multi-relational data
- A new backtracking algorithm for generating the family of maximal independent sets of a graph
- Version spaces and the consistency problem
- Listing closed sets of strongly accessible set systems with applications to data mining
- A global parallel algorithm for the hypergraph transversal problem
- 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
- Enumerating minimal dominating sets in chordal bipartite graphs
- Generating cut conjunctions in graphs and related problems
- 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
- Generating 3-vertex connected spanning subgraphs
This page was built for publication: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3890128)
