The \textsc{max quasi-independent set} problem

DOI10.1007/S10878-010-9343-5zbMath1244.90230OpenAlexW2170054126MaRDI QIDQ434194

Nicolas Bourgeois, Vangelis Th. Paschos, Ioannis Milis, Giorgio Lucarelli, O. Pottié, Aristotelis Giannakos

Publication date: 10 July 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9343-5

zbMATH Keywords

approximation algorithmsexact algorithmsquasi independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (4)

A review on algorithms for maximum clique problems ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Largest sparse subgraphs of random graphs ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Pathwidth of cubic graphs and exact algorithms
• Clustering and domination in perfect graphs
• The node-deletion problem for hereditary properties is NP-complete
• \(k\)-edge subgraph problems
• Mining market data: a network approach
• Greed is good
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Node-Deletion NP-Complete Problems
• Selected Applications of Minimum Cuts in Networks
• Paths, Stars and the Number Three
• Greedily Finding a Dense Subgraph
• The dense \(k\)-subgraph problem
• A generalization of maximal independent sets

This page was built for publication: The \textsc{max quasi-independent set} problem