Knapsack: connectedness, path, and shortest-path

DOI10.1007/978-3-031-55601-2_11MaRDI QIDQ6547953zbMATH OpenFDO

Authors Palash Dey, Sudeshna Kolay, Sipra Singh

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-55601-2_11

zbMATH Keywords

approximation algorithmgraph algorithmsknapsackparameterised complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A faster parameterized algorithm for pseudoforest deletion
• A new approach on locally checkable problems
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem
• Approximability of partitioning graphs with supply and demand
• Approximation of knapsack problems with conflict and forcing graphs
• Cover by disjoint cliques cuts for the knapsack problem with conflicting items
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Introduction to algorithms.
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On the thinness and proper thinness of a graph
• Parameterized algorithms
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• The Knapsack Problem with Conflict Graphs
• The knapsack problem with special neighbor constraints
• The stable set problem and the thinness of a graph

Cited in

(1)

• Knapsack with vertex cover, set cover, and hitting set

This page was built for publication: Knapsack: connectedness, path, and shortest-path

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