A New Algorithm for Generating All the Maximal Independent Sets

DOI10.1137/0206036zbMATH Open0364.05027DBLPjournals/siamcomp/TsukiyamaIAS77OpenAlexW2089417393WikidataQ56210445 ScholiaQ56210445MaRDI QIDQ4138754FDOQ4138754

Authors: Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, 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)

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

• On the parameterized complexity of coloring graphs in the absence of a linear forest
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Nonparametric estimation of the bivariate CDF for arbitrarily censored data
• Coloring square-free Berge graphs
• Parameterized algorithms for finding square roots
• The maximum clique problem
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Colouring vertices of triangle-free graphs without forests
• Disconnecting graphs by removing vertices: a polyhedral approach
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Graphs without large apples and the maximum weight independent set problem
• The Maximum Independent Set Problem in Planar Graphs
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On the average-case complexity of parameterized clique
• Graphs of separability at most 2
• Mod/Resc parsimony inference: theory and application
• Exact algorithms for exact satisfiability and number of perfect matchings
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• Strong cliques in diamond-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• A superclass of edge-path-tree graphs with few cliques
• Intersection graphs of paths in a tree
• The complexity of dissociation set problems in graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Split dimension of graphs
• Enumerating maximal independent sets with applications to graph colouring.
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Approximately counting locally-optimal structures
• Generating bicliques of a graph in lexicographic order
• Consensus algorithms for the generation of all maximal bicliques
• A note on the problem of reporting maximal cliques
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Boundary classes of graphs for the dominating set problem
• A graph-theoretic method for organizing overlapping clusters into trees, multiple trees, or extended trees
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A unified approach to recognize squares of split graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Colouring vertices of triangle-free graphs
• Graphs of separability at most two: structural characterizations and their consequences
• An upper bound for the number of maximal independent sets in a graph
• On generating all maximal independent sets
• Independent domination in finitely defined classes of graphs
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
• Recognizing Helly edge-path-tree graphs and their clique graphs
• Graphs with maximal induced matchings of the same size
• Feedback vertex sets in tournaments
• The generalized linear complementarity problem and an algorithm to find all its solutions
• Recognizing clique graphs of directed and rooted path graphs
• Complexity of finding graph roots with girth conditions
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• On hereditary clique-Helly self-clique graphs
• jHoles: a tool for understanding biological complex networks via clique weight rank persistent homology
• A polyhedral approach to sequence alignment problems
• An exact algorithm for the pallet loading problem
• Generating dual-bounded hypergraphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Computational aspects of monotone dualization: a brief survey
• Graph theoretical structures in logic programs and default theories
• Intersection graphs of Helly families of subtrees
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Independent domination in hereditary classes
• Trimmed Moebius inversion and graphs of bounded degree
• 4-coloring \(H\)-free graphs when \(H\) is small
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Solving haplotyping inference parsimony problem using a new basic polynomial formulation
• On enumerating all minimal solutions of feedback problems
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• Hypergraph imaging: An overview
• The \(k\)-edge intersection graphs of paths in a tree
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• Enumeration aspects of maximal cliques and bicliques
• Maximal independent sets in a generalisation of caterpillar graph
• A new decomposition technique for maximal clique enumeration for sparse graphs
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Approximately Counting Locally-Optimal Structures
• On the complexity of enumerating pseudo-intents
• Efficiently enumerating all maximal cliques with bit-parallelism
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Maximal independent sets in caterpillar graphs
• Fast maximal cliques enumeration in sparse graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• On balanced graphs
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Average polynomial time complexity of some NP-complete problems
• Simple games versus weighted voting games: bounding the critical threshold value
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• On cycle transversals and their connected variants in the absence of a small linear forest
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Coloring permutation graphs in parallel
• Recognizing max-flow min-cut path matrices
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Theoretical underpinnings for maximal clique enumeration on perturbed graphs
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs

This page was built for publication: A New Algorithm for Generating All the Maximal Independent Sets

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