scientific article; zbMATH DE number 7274190

zbMath1473.68120MaRDI QIDQ5133215

Olivier Hudry, Antoine C. Lobstein

Publication date: 12 November 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

decision problemsgraph theorydominationNP-hardnesscomplexity theoryvertex coverspolynomial reductiondominating codesBoolean satisfiability problemsuniqueness of (optimal) solution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational aspects of satisfiability (68R07)

Related Items (1)

Some rainbow problems in graphs have complexity equivalent to satisfiability problems

This page was built for publication: