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

DOI10.1007/s12190-020-01459-9zbMath1475.05139OpenAlexW3102868954MaRDI QIDQ2053252

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

polynomial time algorithmdominationinterval graphstotal dominationsemitotal domination

Mathematics Subject Classification ID

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

Related Items (1)

A linear-time algorithm for semitotal domination in strongly chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertices contained in all or in no minimum semitotal dominating set of a tree
• A survey of selected recent results on total domination in graphs
• A unified approach to domination problems on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the semitotal domination number of line graphs
• Algorithmic aspects of semitotal domination in graphs
• Edge weighting functions on semitotal dominating sets
• On matching and semitotal domination in graphs
• Semitotal domination in trees
• Complexity and approximation ratio of semitotal domination in graphs
• Total Domination in Graphs
• Semitotal domination in claw-free cubic graphs

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