Counting and enumerating independent sets with applications to combinatorial optimization problems
type: Item
instance of: scholarly article
title: Counting and enumerating independent sets with applications to combinatorial optimization problems
zbMATH Open document ID: 1444.05068
author: Frank Gurski
author: Carolin Rehs
published in: Mathematical Methods of Operations Research
publication date: 2020-08-03T00:00:00Z
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7227041
zbMATH Keywords: knapsack problem
zbMATH Keywords: multidimensional knapsack problem
zbMATH Keywords: threshold graphs
zbMATH Keywords: independent sets
MaRDI profile type: Publication
full work available at URL: s00186-019-00696-4
OpenAlex ID: W2995205409
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: Ond-threshold graphs andd-dimensional bin packing
cites work: Q4165164
cites work: On the product knapsack problem
cites work: The multidimensional 0-1 knapsack problem: an overview.
cites work: Q3328583
cites work: A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time
cites work: Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
cites work: Knapsack problems: a parameterized point of view
cites work: The splittance of a graph
cites work: Q5503435
cites work: Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
cites work: Threshold graphs and related topics
cites work: On cliques in graphs
cites work: Counting the number of independent sets in chordal graphs
cites work: Q5708515
cites work: The Knapsack Problem with Conflict Graphs
cites work: Approximation of knapsack problems with conflict and forcing graphs
cites work: Q3342477
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: The complexity of counting in sparse, regular, and planar graphs
cites work: The Complexity of the Partial Order Dimension Problem
DOI: 10.1007/S00186-019-00696-4
Recommended article: Extremal problems for independent set enumeration
Recommended article: Counting independent sets in graphs of hyperplane arrangements
Recommended article: Q5461588
Recommended article: Enumerating maximal independent sets with applications to graph colouring.
Recommended article: A Worst-Case Time Upper Bound for Counting the Number of Independent Sets
Recommended article: Counting Independent Sets in Hypergraphs
Recommended article: Counting independent sets in cocomparability graphs
Recommended article: Q5740795
Recommended article: A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs
Recommended article: Q4828946
description: scientific article; zbMATH DE number 7227041