Approximating weighted neighborhood independent sets

DOI10.1016/j.ipl.2017.09.014zbMath1419.68217OpenAlexW2762269748MaRDI QIDQ1679903

Min Chih Lin, Saveliy Vasiliev, Julián Mestre

Publication date: 22 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.09.014

zbMATH Keywords

graph algorithmsapproximation algorithmsweighted neighborhood independent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

• Neighborhood perfect graphs
• Complement reducible graphs
• Neighbourhood-perfect line graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• On tree-constrained matchings and generalizations
• A Linear Recognition Algorithm for Cographs
• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• Minimal non-neighborhood-perfect graphs
• Non-approximability results for optimization problems on bounded degree instances
• Algorithmic Aspects of Neighborhood Numbers