Complexity and algorithms for semipaired domination in graphs

DOI10.1007/s00224-020-09988-3zbMath1503.68223arXiv1904.00964OpenAlexW3033103597MaRDI QIDQ5918285

Michael A. Henning, Vikash Tripathi, Arti Pandey

Publication date: 11 June 2021

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmapproximation algorithmNP-completenessbipartite graphschordal graphsNP-completedominationinterval graphssemipaired domination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

Semipaired Domination in Some Subclasses of Chordal Graphs ⋮ Bounds on the semipaired domination number of graphs with minimum degree at least two ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ Unique minimum semipaired dominating sets in trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Perfect graphs involving semitotal and semipaired domination
• Approximation hardness of dominating set problems in bounded degree graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Semipaired domination in claw-free cubic graphs
• Graphs with large semipaired domination number
• Paired-domination in graphs
• Total Domination in Graphs
• Analytical approach to parallel repetition
• Complexity and algorithms for semipaired domination in graphs

This page was built for publication: Complexity and algorithms for semipaired domination in graphs