Aspects of upper defensive alliances

DOI10.1016/j.dam.2018.05.061zbMath1476.05149OpenAlexW2810141563WikidataQ59864867 ScholiaQ59864867MaRDI QIDQ2026328

Zsolt Tuza, Cristina Bazgan, Henning Fernau

Publication date: 19 May 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/105500/1/Bazgan-Fernau-Tuza-Aspects_of_Upper_Defensive_Alliances.pdf

zbMATH Keywords

NP-hardnessapproximabilitydefensive alliancegraphs of bounded average degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Related Items (3)

Parameterized complexity of locally minimal defensive alliances ⋮ Globally minimal defensive alliances ⋮ Alliances and Related Domination Parameters

Cites Work

• Satisfactory graph partition, variants, and generalizations
• On the complement graph and defensive \(k\)-alliances
• Defensive \(k\)-alliances in graphs
• Which problems have strongly exponential complexity?
• Approximation hardness of edge dominating set problems
• Cycle Domination, Independence and Irredundance in graphs
• Hardness and approximation of minimum maximal matchings
• Minimum Edge Dominating Sets
• Small Alliances in Graphs
• Edge Dominating Sets in Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Algorithms and Computation
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Unnamed Item
• Unnamed Item

This page was built for publication: Aspects of upper defensive alliances