Counting and enumerating independent sets with applications to combinatorial optimization problems
From MaRDI portal
Publication:784784
DOI10.1007/s00186-019-00696-4zbMath1444.05068OpenAlexW2995205409MaRDI QIDQ784784
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
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