Expanding operators for the independent set problem

DOI10.1134/S1990478913030149MaRDI QIDQ5263812zbMATH OpenOpenAlexFDO

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

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)

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

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)