Aspects of upper defensive alliances

DOI10.1016/J.DAM.2018.05.061MaRDI QIDQ2026328zbMATH OpenOpenAlexWikidataFDO

Authors Cristina Bazgan, Henning Fernau, Zsolt Tuza

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)

Recommendations

• scientific article; zbMATH DE number 2076807
• scientific article; zbMATH DE number 2104820
• Global defensive sets in graphs
• Global defensive alliances in graphs
• On defensive alliances and strong global offensive alliances

Cites work

• scientific article; zbMATH DE number 6843424 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• Algorithms and Computation
• Approximation hardness of edge dominating set problems
• Cycle domination, independence, and irredundance in graphs
• Defensive k-alliances in graphs
• Edge Dominating Sets in Graphs
• Hardness and approximation of minimum maximal matchings
• Minimum Edge Dominating Sets
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• On the complement graph and defensive \(k\)-alliances
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• Satisfactory graph partition, variants, and generalizations
• Small Alliances in Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Which problems have strongly exponential complexity?

Cited in

(14)

• On defensive alliances and strong global offensive alliances
• Parameterized complexity of locally minimal defensive alliances
• On the defensive alliances in graph
• Global defensive sets in graphs
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• The algorithmic complexity of alliances in graphs
• Defensive alliances with prescribed and proscribed vertices
• Small alliances in a weighted graph
• Globally minimal defensive alliances
• Alliances in generalized series parallel graphs
• Small Alliances in Graphs
• Strong alliances in graphs
• scientific article; zbMATH DE number 2076807 (Why is no real title available?)
• Alliances and Related Domination Parameters

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2026328)