Defensive alliances in graphs

DOI10.1016/J.TCS.2022.06.021MaRDI QIDQ2079875zbMATH OpenOpenAlexFDO

Authors Ajinkya Gaikwad, Soumen Maity

Publication date 7 October 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

circle graphdefensive allianceETHfeedback vertex setFPTparameterised complexitytreedepthW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Defensive alliances in graphs of bounded treewidth
• Parameterized complexity of locally minimal defensive alliances
• Globally minimal defensive alliances
• Aspects of upper defensive alliances
• scientific article; zbMATH DE number 2076807

Cites work

• Alliances in graphs of bounded clique-width
• Defensive alliances in graphs of bounded treewidth
• Global alliances and independence in trees
• Global defensive alliances of trees and Cartesian product of paths and cycles
• Global offensive alliances in graphs
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2076807 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Lower bounds based on the exponential time hypothesis
• Offensive \(r\)-alliances in graphs
• On defensive alliances and line graphs
• On structural parameterizations of the offensive alliance problem
• On the complement graph and defensive \(k\)-alliances
• On the global offensive alliance number of a graph
• Parameterized algorithms
• Problems hard for treewidth but easy for stable gonality
• The algorithmic complexity of alliances in graphs
• The complexity of domination problems in circle graphs
• Treewidth. Computations and approximations

Cited in

(15)

• Offensive \(r\)-alliances in graphs
• Defensive alliances in graphs of bounded treewidth
• Globally minimal defensive alliances
• scientific article; zbMATH DE number 5777940 (Why is no real title available?)
• scientific article; zbMATH DE number 6843424 (Why is no real title available?)
• Defensive alliance polynomial
• On defensive alliance in zero-divisor graphs
• scientific article; zbMATH DE number 6475954 (Why is no real title available?)
• Structural parameterization of alliance problems
• Offensive alliances in graphs
• Enumerating minimal defensive alliances
• On the tractability of defensive alliance problem
• Parameterized complexity of locally minimal defensive alliances
• Boundary defensive k-alliances in graphs
• Parameterized complexity of locally minimal defensive alliances

This page was built for publication: Defensive alliances in graphs

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