Algorithms and Hardness for Signed Domination

DOI10.1007/978-3-319-17142-5_38MaRDI QIDQ2948490zbMATH OpenOpenAlexWikidataFDO

Authors Jin-Yong Lin, Sheung-Hung Poon

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-17142-5_38

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 825134
• Algorithms and complexity of signed, minus, and majority domination
• On the complexity of signed and minus total domination in graphs
• Some NP-complete results on signed mixed domination problem
• On the signed domination in graphs
• Kernelization and Lower Bounds of the Signed Domination Problem
• On domination in signed graphs
• scientific article; zbMATH DE number 2080250
• Efficient minus and signed domination in graphs
• scientific article; zbMATH DE number 861417

Cites work

• scientific article; zbMATH DE number 825134 (Why is no real title available?)
• Kernelization and Lower Bounds of the Signed Domination Problem
• Minus domination in small-degree graphs
• On complexities of minus domination

Cited in

(4)

• FPT results for signed domination
• Algorithms and complexity of signed, minus, and majority domination
• Complexity of majority monopoly and signed domination problems
• Kernelization and Lower Bounds of the Signed Domination Problem

This page was built for publication: Algorithms and Hardness for Signed Domination

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