Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs.

Ilan Doron Arad Hadas Shachnai

Published in: CoRR (2023)

Keyphrases

independent set
tight bounds
maximum weight
bipartite graph
upper bound
minimum weight
maximum independent set
weighted graph
multi class
partial order
lower bound
np hard
dynamic programming
worst case
link prediction
undirected graph