Expanding operators for the independent set problem

DOI10.1134/S1990478913030149zbMATH Open1324.05143OpenAlexW2167286094MaRDI QIDQ5263812FDOQ5263812

Authors: D. S. Malyshev 

Publication date: 17 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478913030149

Recommendations

• On the number of independent sets in expanders
• Parameterized extension complexity of independent set and related problems
• Extremal problems for independent set enumeration
• Extension complexity of independent set polytopes
• Expanding the Tutte polynomial of a matroid over the independent sets
• On the complexity of approximating the independent set problem (extended abstract)
• On the complexity of approximating the independent set problem
• Expansion independence in choice problems
• A generalization of maximal independent sets
• On the independent set interdiction problem

zbMATH Keywords

computational complexityindependent set problemeffective algorithmexpanding operator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cited In (1)

• Expansion independence in choice problems

This page was built for publication: Expanding operators for the independent set problem

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