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)

• 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
• 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
• Generating all maximal independent sets on trees in lexicographic order
• Approximation and kernelization for chordal vertex deletion
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Struction revisited
• Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Triangulated neighborhoods in even-hole-free graphs
• The k-Dense Method to Extract Communities from Complex Networks
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Generate all maximal independent sets in permutation graphs
• New results on independent sets in extensions of \(2K_2\)-free graphs
• Stability in \(P_5\)- and banner-free graphs
• Title not available (Why is that?)
• From matchings to independent sets
• In search of the densest subgraph
• Matroid representation of clique complexes
• Clique covering and clique partition in generalizations of line graphs
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• On the thinness and proper thinness of a graph
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• An algorithm for generating all maximal independent subsets of posets
• On some graph classes related to perfect graphs: a survey
• An inequality for polymatroid functions and its applications.
• Maximal independent sets in clique-free graphs
• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
• A stratificational overlapping cluster scheme
• Maximal induced matchings in triangle-free graphs
• A new backtracking algorithm for generating the family of maximal independent sets of a graph
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Squares of Intersection Graphs and Induced Matchings
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• Privacy-preserving data splitting: a combinatorial approach
• Efficient enumeration of maximal induced bicliques
• Coloring \((4K_1,C_4,C_6)\)-free graphs
• Maximal independent sets in caterpillar graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Exact algorithms for minimum weighted dominating induced matching
• Generating toric noncommutative crepant resolutions
• 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
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• 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

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)