Approximating weighted neighborhood independent sets

DOI10.1016/J.IPL.2017.09.014MaRDI QIDQ1679903zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Julián Mestre, Saveliy Vasiliev

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

approximation algorithmsgraph algorithmsweighted neighborhood independent set

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1182757
• A note on the approximation of a minimum-weight maximal independent set
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Approximating independent set in perturbed graphs
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• scientific article; zbMATH DE number 1405687
• Approximating independent sets in sparse graphs
• Weighted domination of independent sets
• Simple and local independent set approximation

Cites work

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

Cited in

(1)

• scientific article; zbMATH DE number 1405687 (Why is no real title available?)

This page was built for publication: Approximating weighted neighborhood independent sets

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