An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs

DOI10.1142/S1793557121500492zbMath1458.05109OpenAlexW3007527189MaRDI QIDQ4985488

Amita Samanta Adhya, Sukumar Mondal, Sambhu Charan Barman

Publication date: 23 April 2021

Published in: Asian-European Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793557121500492

zbMATH Keywords

algorithmspermutation graphs\(k\)-hop connected domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Distance in graphs (05C12)

Related Items (1)

Computation of diameter, radius and center of permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• The \(k\)-tuple twin domination in generalized de Bruijn and Kautz networks
• Paired-domination in inflated graphs
• Minimum 2-tuple dominating set of an interval graph
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• A linear time algorithm for optimal \(k\)-hop dominating set of a tree
• Bounds on the hop domination number of a tree
• An optimal greedy heuristic to color interval graphs
• Locating and paired-dominating sets in 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 polynomial-time algorithm for the paired-domination problem on permutation graphs
• \(k\)-tuple domination in graphs
• An efficient algorithm to find next-to-shortest path on permutation graphs
• Breadth-first traversal of trees and integer sorting in parallel
• Topics on domination
• Weighted domination of cocomparability graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Perfect edge domination and efficient edge domination in graphs
• Paired-domination of trees
• Dynamic monopolies of constant size
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Algorithmic graph theory and perfect graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Paired domination on interval and circular-arc graphs
• On 2-step and hop dominating sets in graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Total Domination and Irredundance in Weighted Interval Graphs
• Incremental modular decomposition
• Total domination in graphs
• Edge Dominating Sets in Graphs
• R -Domination in Graphs
• Paired-domination in graphs
• Total Domination Edge Critical Graphs with Maximum Diameter
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
• An efficient algorithm to solve the distancek-domination problem on permutation graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Depth-First Search and Linear Graph Algorithms
• Domination critical graphs

This page was built for publication: An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs