Alliances in graphs of bounded clique-width

DOI10.1016/j.dam.2017.02.004zbMath1465.05178OpenAlexW2593747529MaRDI QIDQ2030439

Masashi Kiyomi, Yota Otachi

Publication date: 7 June 2021

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

Full work available at URL: https://doi.org/10.1016/j.dam.2017.02.004

zbMATH Keywords

graph algorithmvertex coverallianceclique width

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Defensive alliances in graphs of bounded treewidth ⋮ On structural parameterizations of the offensive alliance problem ⋮ Parameterized intractability of defensive alliance problem ⋮ Structural parameterization of alliance problems ⋮ Parameterized complexity of satisfactory partition problem ⋮ Alliances and Related Domination Parameters ⋮ Defensive alliances in graphs ⋮ Offensive alliances in graphs

Cites Work

• Global defensive alliances of trees and Cartesian product of paths and cycles
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• \(\alpha \)-domination perfect trees
• Offensive \(r\)-alliances in graphs
• On the complement graph and defensive \(k\)-alliances
• An application of simultaneous diophantine approximation in combinatorial optimization
• \(\alpha\)-domination
• Upper bounds to the clique width of graphs
• On the approximability of positive influence dominating set in social networks
• Approximating clique-width and branch-width
• Integer Programming with a Fixed Number of Variables
• Clique-Width is NP-Complete
• Graph Layout Problems Parameterized by Vertex Cover
• Minkowski's Convex Body Theorem and Integer Programming
• A survey on alliances and related parameters in graphs
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Alliances in graphs of bounded clique-width