3 papers
cs.DS2026
Dominating Set Knapsack: Profit Optimization on Dominating Sets
Sipra Singh
In a large-scale network, we want to choose some influential nodes to make a profit by paying some cost within a limited budget so that we do not have to spend more budget on some…
cs.DS2024
Knapsack with Vertex Cover, Set Cover, and Hitting Set
Palash Dey, Ashlesha Hota, Sudeshna Kolay +1
Given an undirected graph , with vertex weights , vertex values , a knapsack size , a…
cs.DS2024
Knapsack: Connectedness, Path, and Shortest-Path
Palash Dey, Sudeshna Kolay, Sipra Singh
We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs t…