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
• 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
• 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
• 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
• 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 maximal cliques with connectivity constraints in directed graphs
• Efficient parallel algorithms for parameterized problems
• Maximal strongly connected cliques in directed graphs: algorithms and bounds
• Title not available (Why is that?)
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Maximal independent sets in grid graphs
• Maximum dissociation sets in subcubic trees
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Generating clause sequences of a CNF formula
• Recognizing clique graphs of directed edge path graphs
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
• Characterization of classical graph classes by weighted clique graphs
• Finding cliques in social networks: a new distribution-free model
• On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Fuzzy graphs and networks repairs
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Map graphs having witnesses of large girth
• Complexity and polynomially solvable special cases of QUBO
• Output-size sensitiveness of OBDD construction through maximal independent set problem
• Title not available (Why is that?)
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Recognizing map graphs of bounded treewidth
• Minimum cost flow problem with conflicts
• Translating between the representations of a ranked convex geometry
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• On the generation of bicliques of a graph
• Finding cliques in social networks: a new distribution-free model
• On the approximability of the minimum weight \(t\)-partite clique problem
• Listing all spanning trees in Halin graphs -- sequential and parallel view
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• Local multiple alignment via subgraph enumeration
• Representations of partial leaf sets in phylogenetic tree space
• Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Decision-based scenario clustering for decision-making under uncertainty
• Constant amortized time enumeration of Eulerian trails
• Unique key Horn functions
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Understanding the complexity of axiom pinpointing in lightweight description logics
• Using Fifth Generation Tools for Solving the Clique Number Problem
• Proximity Search for Maximal Subgraph Enumeration
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• A new approximate cluster deletion algorithm for diamond-free graphs
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints

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)