An O(n+m) time algorithm for computing a minimum semitotal dominating set in an interval graph

DOI10.1007/S12190-020-01459-9MaRDI QIDQ2053252zbMATH OpenOpenAlexFDO

Authors Saikat Pal, Dina Pradhan

Publication date 29 November 2021

Published in Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s12190-020-01459-9

zbMATH Keywords

dominationinterval graphspolynomial time algorithmsemitotal dominationtotal domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithmic aspects of semitotal domination in graphs
• A linear-time algorithm for semitotal domination in strongly chordal graphs
• The semitotal domination problem in block graphs
• Total domination in interval graphs

Cites work

• A survey of selected recent results on total domination in graphs
• A unified approach to domination problems on interval graphs
• Algorithmic aspects of semitotal domination in graphs
• Complexity and approximation ratio of semitotal domination in graphs
• Edge weighting functions on semitotal dominating sets
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• On matching and semitotal domination in graphs
• On the semitotal domination number of line graphs
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs
• Semitotal domination in trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Total domination in graphs
• Vertices contained in all or in no minimum semitotal dominating set of a tree

Cited in

(2)

• Algorithmic aspects of semitotal domination in graphs
• A linear-time algorithm for semitotal domination in strongly chordal graphs

This page was built for publication: An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph

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