A New Algorithm for Generating All the Maximal Independent Sets

DOI10.1137/0206036MaRDI QIDQ4138754zbMATH OpenOpenAlexDBLPWikidataFDO

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)

• Translating between the representations of a ranked convex geometry
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• Colouring vertices of triangle-free graphs
• Graphs of separability at most two: structural characterizations and their consequences
• Recognizing map graphs of bounded treewidth
• Minimum cost flow problem with conflicts
• On the generation of bicliques of a graph
• On generating all maximal independent sets
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
• Maximal independent sets in clique-free graphs
• An upper bound for the number of maximal independent sets in a graph
• Independent domination in finitely defined classes of graphs
• Graphs with maximal induced matchings of the same size
• Finding cliques in social networks: a new distribution-free model
• On the approximability of the minimum weight \(t\)-partite clique problem
• Recognizing Helly edge-path-tree graphs and their clique graphs
• Listing all spanning trees in Halin graphs -- sequential and parallel view
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• The generalized linear complementarity problem and an algorithm to find all its solutions
• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Recognizing clique graphs of directed and rooted path graphs
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Feedback vertex sets in tournaments
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• Complexity of finding graph roots with girth conditions
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Local multiple alignment via subgraph enumeration
• Representations of partial leaf sets in phylogenetic tree space
• jHoles: a tool for understanding biological complex networks via clique weight rank persistent homology
• On hereditary clique-Helly self-clique graphs
• ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
• A stratificational overlapping cluster scheme
• Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs
• A new backtracking algorithm for generating the family of maximal independent sets of a graph
• A polyhedral approach to sequence alignment problems
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• An exact algorithm for the pallet loading problem
• Computational aspects of monotone dualization: a brief survey
• Graph theoretical structures in logic programs and default theories
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Generating dual-bounded hypergraphs
• Intersection graphs of Helly families of subtrees
• Decision-based scenario clustering for decision-making under uncertainty
• Constant amortized time enumeration of Eulerian trails
• Unique key Horn functions
• Independent domination in hereditary classes
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Trimmed Moebius inversion and graphs of bounded degree
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Understanding the complexity of axiom pinpointing in lightweight description logics
• 4-coloring \(H\)-free graphs when \(H\) is small
• Using Fifth Generation Tools for Solving the Clique Number Problem
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• Solving haplotyping inference parsimony problem using a new basic polynomial formulation
• Squares of Intersection Graphs and Induced Matchings
• Privacy-preserving data splitting: a combinatorial approach
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Proximity Search for Maximal Subgraph Enumeration
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• On enumerating all minimal solutions of feedback problems
• A new approximate cluster deletion algorithm for diamond-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• Co-bipartite neighborhood edge elimination orderings
• Path Problems in Complex Networks
• Efficient enumeration of maximal induced bicliques
• The \(k\)-edge intersection graphs of paths in a tree
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Hypergraph imaging: An overview
• Tightening a copositive relaxation for standard quadratic optimization problems
• Monopolar graphs: complexity of computing classical graph parameters
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Enumeration aspects of maximal cliques and bicliques
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• Maximal independent sets in a generalisation of caterpillar graph
• Coloring \((4K_1,C_4,C_6)\)-free graphs
• Maximum weight independent set for claw-free graphs in polynomial time
• On minimal forbidden subgraph characterizations of balanced graphs
• A new decomposition technique for maximal clique enumeration for sparse graphs
• On the complexity of enumerating pseudo-intents
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Efficiently enumerating all maximal cliques with bit-parallelism
• Approximately Counting Locally-Optimal Structures
• Reconfiguration of cliques in a graph
• 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
• Fast maximal cliques enumeration in sparse graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Clique-perfectness and balancedness of some graph classes
• 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
• Generating toric noncommutative crepant resolutions
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• 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

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)