On complexities of minus domination

DOI10.1016/J.DISOPT.2016.04.002zbMath1387.90264OpenAlexW3022416027MaRDI QIDQ1751171

Luérbio Faria, Hsiang-Hsuan Liu, Ton Kloks, Yue-Li Wang, Tao-Ming Wang, Wing-Kai Hon

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.04.002

zbMATH Keywords

chordal graphdominationminus dominationfixed-parameter tractable\(d\)-degenerate graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Algorithms and Complexity of Signed, Minus, and Majority Domination ⋮ Signed and Minus Dominating Functions in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Practical and efficient split decomposition via graph-labelled trees
• Domination, independent domination, and duality in strongly chordal graphs
• A note on domination and minus domination numbers in cubic graphs
• Upper minus domination in a claw-free cubic graph
• Remarks on the minus (signed) total domination in graphs
• Variations of \(Y\)-dominating functions on graphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Minus domination in graphs
• Algorithmic aspects of majority domination
• Efficient minus and signed domination in graphs
• The difference between the domination number and the minus domination number of a cubic graph
• The extremal function for complete minors
• The algorithmic complexity of minus domination in graphs
• A refined search tree technique for dominating set on planar graphs
• Signed and Minus Domination in Complete Multipartite Graphs
• Linear Time Split Decomposition Revisited
• Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
• On the Minus Domination Number of Graphs
• Signed and minus domination in bipartite graphs
• Planar Capacitated Dominating Set Is W[1-Hard]
• Totally-Balanced and Greedy Matrices
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A survey on alliances and related parameters in graphs
• Kernelization and Lower Bounds of the Signed Domination Problem
• Finding Branch-Decompositions and Rank-Decompositions
• Minus domination in small-degree graphs
• Lower bound on the minus-domination number

This page was built for publication: On complexities of minus domination