A New Algorithm for Generating All the Maximal Independent Sets

DOI10.1137/0206036zbMath0364.05027OpenAlexW2089417393WikidataQ56210445 ScholiaQ56210445MaRDI QIDQ4138754

Hiromu Ariyoshi, Mikio Ide, Shuji Tsukiyama, Isao Shirakawa

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206036

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Independent domination in hereditary classes, Coloring permutation graphs in parallel, Intersection graphs of paths in a tree, Independent sets of maximum weight in (\(p,q\))-colorable graphs., Generating all maximal independent sets on trees in lexicographic order, Boundary classes of graphs for the dominating set problem, Dual-bounded generating problems: Weighted transversals of a hypergraph, jHoles: a tool for understanding biological complex networks via clique weight rank persistent homology, Approximately counting locally-optimal structures, Clique covering and clique partition in generalizations of line graphs, Average polynomial time complexity of some NP-complete problems, On enumerating all minimal solutions of feedback problems, A unified approach to recognize squares of split graphs, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, Recognizing max-flow min-cut path matrices, Efficiently enumerating all maximal cliques with bit-parallelism, On generating all maximal independent sets, The worst-case time complexity for generating all maximal cliques and computational experiments, Graphs with maximal induced matchings of the same size, A sufficient condition to extend polynomial results for the maximum independent set problem, A graph-theoretic method for organizing overlapping clusters into trees, multiple trees, or extended trees, New applications of clique separator decomposition for the maximum weight stable set problem, Triangulated neighborhoods in even-hole-free graphs, Intersection graphs of Helly families of subtrees, Homothetic polygons and beyond: maximal cliques in intersection graphs, Enumeration and maximum number of minimal connected vertex covers in graphs, Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity, Understanding the complexity of axiom pinpointing in lightweight description logics, Generating toric noncommutative crepant resolutions, Co-bipartite neighborhood edge elimination orderings, Independent domination in finitely defined classes of graphs, Graphs of separability at most 2, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, Mod/Resc parsimony inference: theory and application, An algorithm for generating all maximal independent subsets of posets, On the complexity of enumerating pseudo-intents, Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time, An inequality for polymatroid functions and its applications., Fast maximal cliques enumeration in sparse graphs, A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically, On easy and hard hereditary classes of graphs with respect to the independent set problem, Struction revisited, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, \(P_{5}\)-free augmenting graphs and the maximum stable set problem, Some results on maximum stable sets in certain \(P_{5}\)-free graphs, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, On the parameterized complexity of coloring graphs in the absence of a linear forest, Trimmed Moebius inversion and graphs of bounded degree, Coloring square-free Berge graphs, Solving haplotyping inference parsimony problem using a new basic polynomial formulation, Split dimension of graphs, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Graph theoretical structures in logic programs and default theories, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, A new decomposition technique for maximal clique enumeration for sparse graphs, Computational aspects of monotone dualization: a brief survey, Maximal strongly connected cliques in directed graphs: algorithms and bounds, Efficient enumeration of maximal induced bicliques, Simple games versus weighted voting games: bounding the critical threshold value, Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs, Maximal independent sets in a generalisation of caterpillar graph, A note on the problem of reporting maximal cliques, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, A polynomial Turing-kernel for weighted independent set in bull-free graphs, Exact algorithms for minimum weighted dominating induced matching, Exact algorithms for exact satisfiability and number of perfect matchings, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Maximum regular induced subgraphs in \(2P_3\)-free graphs, In search of the densest subgraph, Independent sets in extensions of 2\(K_{2}\)-free graphs, Enumerating maximal independent sets with applications to graph colouring., Theoretical underpinnings for maximal clique enumeration on perturbed graphs, Consensus algorithms for the generation of all maximal bicliques, Generating bicliques of a graph in lexicographic order, Exact solution algorithms for the maximum flow problem with additional conflict constraints, Translating between the representations of a ranked convex geometry, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Privacy-preserving data splitting: a combinatorial approach, An improved upper bound on maximal clique listing via rectangular fast matrix multiplication, Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs, The generalized linear complementarity problem and an algorithm to find all its solutions, Graphs without large apples and the maximum weight independent set problem, Independent sets in \((P_4+P_4\),triangle)-free graphs, An exact algorithm for the pallet loading problem, Enumeration aspects of maximal cliques and bicliques, Updating the complexity status of coloring graphs without a fixed induced linear forest, Colouring vertices of triangle-free graphs without forests, Maximal independent sets in caterpillar graphs, A superclass of edge-path-tree graphs with few cliques, Recognizing clique graphs of directed and rooted path graphs, Stability in \(P_5\)- and banner-free graphs, Counting and enumerating independent sets with applications to combinatorial optimization problems, A new backtracking algorithm for generating the family of maximal independent sets of a graph, A polyhedral approach to sequence alignment problems, A stratificational overlapping cluster scheme, On the stable set problem in special \(P_{5}\)-free graphs, Recognizing clique graphs of directed edge path graphs, Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms, The maximum clique problem, Parameterized algorithms for finding square roots, 4-Coloring H-Free Graphs When H Is Small, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Proximity Search for Maximal Subgraph Enumeration, Approximately Counting Locally-Optimal Structures, Complexity and Polynomially Solvable Special Cases of QUBO, Tightening a copositive relaxation for standard quadratic optimization problems, Map graphs having witnesses of large girth, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs, Matroid representation of clique complexes, Towards constant-factor approximation for chordal/distance-hereditary vertex deletion, Path Problems in Complex Networks, ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS, New results on independent sets in extensions of \(2K_2\)-free graphs, Clique-perfectness and balancedness of some graph classes, Monopolar graphs: complexity of computing classical graph parameters, Decision-based scenario clustering for decision-making under uncertainty, From matchings to independent sets, An algorithm for finding a maximum weighted independent set in an arbitrary graph, On the thinness and proper thinness of a graph, Unique key Horn functions, Constant amortized time enumeration of Eulerian trails, Approximation and Kernelization for Chordal Vertex Deletion, On some graph classes related to perfect graphs: a survey, Maximal independent sets in clique-free graphs, Polynomial-delay and polynomial-space enumeration of large maximal matchings, On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs, Minimum cost flow problem with conflicts, Output-size sensitiveness of OBDD construction through maximal independent set problem, Coloring \((4K_1,C_4,C_6)\)-free graphs, Generate all maximal independent sets in permutation graphs, The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\), Finding Cliques in Social Networks: A New Distribution-Free Model, Unnamed Item, Complexity of finding graph roots with girth conditions, Maximum dissociation sets in subcubic trees, Recognizing map graphs of bounded treewidth, Listing all spanning trees in Halin graphs — sequential and Parallel view, Maximal independent sets in grid graphs, On the Approximability of the Minimum Weight $t$-partite Clique Problem, Feedback Vertex Sets in Tournaments, Reconfiguration of cliques in a graph, Unnamed Item, Unnamed Item, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications, Generating clause sequences of a CNF formula, Characterization of classical graph classes by weighted clique graphs, Listing Maximal Subgraphs Satisfying Strongly Accessible Properties, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Listing Maximal Independent Sets with Minimal Space and Bounded Delay, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Genetic algorithmic approach to find the maximum weight independent set of a graph, The \(k\)-edge intersection graphs of paths in a tree, On hereditary clique-Helly self-clique graphs, A parallel algorithm to generate all maximal independent sets on permutation graphs, Disconnecting graphs by removing vertices: a polyhedral approach, Generating dual-bounded hypergraphs, Polynomial algorithm for finding the largest independent sets in graphs without forks, An upper bound for the number of maximal independent sets in a graph, The Maximum Independent Set Problem in Planar Graphs, Recognizing Helly edge-path-tree graphs and their clique graphs, The complexity of dissociation set problems in graphs, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Colouring Vertices of Triangle-Free Graphs, Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Hypergraph imaging: An overview, Local multiple alignment via subgraph enumeration, On the generation of bicliques of a graph, Maximal Induced Matchings in Triangle-Free Graphs, On cycle transversals and their connected variants in the absence of a small linear forest, Representations of Partial Leaf Sets in Phylogenetic Tree Space, A new approximate cluster deletion algorithm for diamond-free graphs, Strong cliques in diamond-free graphs, Unnamed Item, Parallel Algorithm for Enumerating Maximal Cliques in Complex Network, The k-Dense Method to Extract Communities from Complex Networks, Nonparametric estimation of the bivariate CDF for arbitrarily censored data, Using Fifth Generation Tools for Solving the Clique Number Problem, On minimal forbidden subgraph characterizations of balanced graphs, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Fuzzy graphs and networks repairs, Unnamed Item, Unnamed Item, Efficient parallel algorithms for parameterized problems, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Parameterized complexity of the maximum independent set problem and the speed of hereditary properties, On balanced graphs, On the average-case complexity of parameterized clique, Squares of Intersection Graphs and Induced Matchings, On maximum independent set of categorical product and ultimate categorical ratios of graphs, An efficient algorithm to generate all maximal independent sets on trapezoid graphs