Defensive alliances in graphs of bounded treewidth

DOI10.1016/j.dam.2018.04.001zbMath1401.05211arXiv1707.04251OpenAlexW2964132521MaRDI QIDQ1627877

Stefan Woltran, Bernhard Bliem

Publication date: 3 December 2018

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

Full work available at URL: https://arxiv.org/abs/1707.04251

zbMATH Keywords

treewidthparameterized complexitydefensive alliance

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)

Related Items (10)

On structural parameterizations of the offensive alliance problem ⋮ Globally minimal defensive alliances ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Parameterized intractability of defensive alliance problem ⋮ Structural parameterization of alliance problems ⋮ Extended MSO model checking via small vertex integrity ⋮ Alliances and Related Domination Parameters ⋮ Algorithms and Complexity of Alliances in Graphs ⋮ Defensive alliances in graphs ⋮ Offensive alliances in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global defensive alliances of trees and Cartesian product of paths and cycles
• Complexity of secure sets
• Alliances in graphs of bounded clique-width
• Complexity of Secure Sets
• Capacitated Domination and Covering: A Parameterized Perspective

This page was built for publication: Defensive alliances in graphs of bounded treewidth