An efficient algorithm to solve the distance k-domination problem on permutation graphs

DOI10.1080/09720529.2014.986906MaRDI QIDQ5069774zbMATH OpenOpenAlexFDO

Authors Akul Rana, Anita Pal, Madhumangal Pal

Publication date 19 April 2022

Published in Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/09720529.2014.986906

zbMATH Keywords

\(k\)-dominationanalysis of algorithmscaterpillardesign of algorithmspermutation graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• A note on distance domination numbers of graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Complexity of distance paired-domination problem in graphs
• An efficient algorithm for distance total domination in block graphs
• scientific article; zbMATH DE number 1222845

Cites work

• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Domination in permutation graphs
• Dominations in trapezoid graphs
• Fast algorithms for the dominating set problem on permutation graphs
• Finding a minimum independent dominating set in a permutation graph
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 146666 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 2191988 (Why is no real title available?)
• Introduction to ``Topics on Domination
• On powers of m-trapezoid graphs
• Relations between packing and covering numbers of a tree
• The 2-neighbourhood covering problem on permutation graphs
• The k-neighbor domination problem

Cited in

(12)

• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• Distance domination in graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• A labeling algorithm for distance domination on block graphs
• An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• An efficient algorithm for distance total domination in block graphs
• Edge-vertex domination on interval graphs
• Computation of minimum d-hop connected dominating set of trees in O(n) time
• An optimal algorithm for computing minimum k-hop dominating set of permutation graphs
• A new approach for the domination problem on permutation graphs

This page was built for publication: An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs

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