Maximum Weighted Independent Sets with a Budget

DOI10.1007/978-3-319-53007-9_23zbMath1485.68187arXiv1506.07773OpenAlexW2964003494MaRDI QIDQ2971655

Unnamed Author, Rogers Mathew, Tushar Kalra, Sudebkumar Prasant Pal

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.07773

zbMATH Keywords

approximation algorithmindependent setNP-hardnesscoverageinapproximabilitypartial vertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (1)

The transportation problem with conflicts

Cites Work

• Approximating maximum independent sets by excluding subgraphs
• Some simplified NP-complete graph problems
• On approximation of max-vertex-cover
• The maximum vertex coverage problem on bipartite graphs
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Approximation algorithms for partial covering problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum Weighted Independent Sets with a Budget