Complexity of the max cut problem with the minimal domination constraint

DOI10.33048/daio.2022.29.706zbMath1506.68086OpenAlexW4221133148MaRDI QIDQ5878608

Vladimir Vladimirovich Voroshilov

Publication date: 21 February 2023

Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/da1289

zbMATH Keywords

approximationcutsetweighted graphdominating setoptimization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• On the max min vertex cover problem
• On the computational complexity of upper fractional domination
• Max-Cut Under Graph Constraints
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of the max cut problem with the minimal domination constraint