Algorithmic aspects of upper paired-domination in graphs

DOI10.1016/j.tcs.2019.10.045zbMath1436.68242OpenAlexW2983456581WikidataQ126834989 ScholiaQ126834989MaRDI QIDQ2283034

Michael A. Henning, Dinabandhu Pradhan

Publication date: 27 December 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.10.045

zbMATH Keywords

polynomial-time algorithmNP-completedominationAPX-completepaired dominationupper paired domination

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (6)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ In)approximability of Maximum Minimal FVS ⋮ Paired-domination problem on distance-hereditary graphs ⋮ (In)approximability of maximum minimal FVS ⋮ Paired Domination in Graphs ⋮ Upper paired domination versus upper domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth of chain graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Upper paired-domination in claw-free graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A linear time recognition algorithm for proper interval graphs
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Distance paired-domination problems on subclasses of chordal graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Optimization, approximation, and complexity classes
• Computing a minimum paired-dominating set in strongly orderable graphs
• The many facets of upper domination
• Complexity of distance paired-domination problem in graphs
• Paired-domination of trees
• Threshold graphs and related topics
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Edge weighting functions on semitotal dominating sets
• Paired domination on interval and circular-arc graphs
• Distance paired domination numbers of graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• On the Complexity Landscape of the Domination Chain
• Upper Domination: Complexity and Approximation
• The paired-domination and the upper paired-domination numbers of graphs
• Paired-domination in graphs
• Total Domination in Graphs
• Edge Weighting Functions on Dominating Sets
• Upper total domination versus upper paired-domination

This page was built for publication: Algorithmic aspects of upper paired-domination in graphs