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

DOI10.1080/09720529.2014.986906zbMath1495.05321OpenAlexW2440158214MaRDI QIDQ5069774

Akul Rana, Madhumangal Pal, Anita 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

analysis of algorithmsdesign of algorithmscaterpillarpermutation graph\(k\)-domination

Mathematics Subject Classification ID

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

Related Items (4)

Unnamed Item ⋮ Distance Domination in Graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems

Cites Work

• Introduction to ``Topics on Domination
• The k-neighbor domination problem
• Finding a minimum independent dominating set in a permutation graph
• Relations between packing and covering numbers of a tree
• Dominations in trapezoid graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• On powers of \(m\)-trapezoid graphs
• Fast algorithms for the dominating set problem on permutation graphs
• Domination in permutation graphs
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient algorithm to solve the distancek-domination problem on permutation graphs