Counting and enumerating independent sets with applications to combinatorial optimization problems

DOI10.1007/S00186-019-00696-4MaRDI QIDQ784784zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Carolin Rehs

Publication date 3 August 2020

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-019-00696-4

zbMATH Keywords

knapsack problemindependent setsthreshold graphsmultidimensional knapsack problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Exact enumeration problems, generating functions (05A15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• Extremal problems for independent set enumeration
• Counting independent sets in graphs of hyperplane arrangements
• scientific article; zbMATH DE number 2188478
• Enumerating maximal independent sets with applications to graph colouring.
• A Worst-Case Time Upper Bound for Counting the Number of Independent Sets
• Counting Independent Sets in Hypergraphs
• Counting independent sets in cocomparability graphs
• Counting the maximal independent sets in power set graphs
• A new method for enumerating independent sets of a fixed size in general graphs
• scientific article; zbMATH DE number 2119675

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3875168 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 2230224 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A graph theoretic approach to solve special knapsack problems in polynomial time
• Approximation of knapsack problems with conflict and forcing graphs
• Counting the number of independent sets in chordal graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Knapsack problems: a parameterized point of view
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On cliques in graphs
• On the product knapsack problem
• Ond-threshold graphs andd-dimensional bin packing
• Partitions of graphs into one or two independent sets and cliques
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• The Complexity of the Partial Order Dimension Problem
• The Knapsack Problem with Conflict Graphs
• The complexity of counting in sparse, regular, and planar graphs
• The multidimensional 0-1 knapsack problem: an overview.
• The splittance of a graph
• Threshold graphs and related topics

Cited in

(6)

• A graph theoretic approach to solve special knapsack problems in polynomial time
• Counting kernels in directed graphs with arbitrary orientations
• On computing minimal independent support and its applications to sampling and counting
• Ond-threshold graphs andd-dimensional bin packing
• Independence number and the complexity of families of sets
• Threshold arrangements and the knapsack problem

This page was built for publication: Counting and enumerating independent sets with applications to combinatorial optimization problems

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