Expanding operators for the independent set problem

DOI10.1134/S1990478913030149zbMATH Open1324.05143OpenAlexW2167286094MaRDI QIDQ5263812

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)

Related Items (1)

Expansion independence in choice problems

Recommendations

• Title not available (Why is that?) 👍 👎
• Extremal problems for independent set enumeration 👍 👎
• On the complexity of approximating the independent set problem 👍 👎
• Expansion independence in choice problems 👍 👎
• Parameterized extension complexity of independent set and related problems 👍 👎
• Extension Complexity of Independent Set Polytopes 👍 👎
• On the number of independent sets in expanders 👍 👎
• On the Independent Set Interdiction Problem 👍 👎
• On the complexity of approximating the independent set problem 👍 👎
• A generalization of maximal independent sets 👍 👎

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)