Counting and enumerating independent sets with applications to combinatorial optimization problems

DOI10.1007/s00186-019-00696-4zbMath1444.05068OpenAlexW2995205409MaRDI QIDQ784784

Carolin Rehs, Frank Gurski

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting the number of independent sets in chordal graphs
• The splittance of a graph
• The multidimensional 0-1 knapsack problem: an overview.
• On the product knapsack problem
• Threshold graphs and related topics
• Partitions of graphs into one or two independent sets and cliques
• Approximation of knapsack problems with conflict and forcing graphs
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Knapsack problems: a parameterized point of view
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Ond-threshold graphs andd-dimensional bin packing
• The Knapsack Problem with Conflict Graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• The Complexity of the Partial Order Dimension Problem
• A New Algorithm for Generating All the Maximal Independent Sets
• A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time
• On cliques in graphs