An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
From MaRDI portal
Publication:4985488
DOI10.1142/S1793557121500492zbMATH Open1458.05109OpenAlexW3007527189MaRDI QIDQ4985488FDOQ4985488
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
Recommendations
- An optimal algorithm to find minimum \(k\)-hop dominating set of interval graphs
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- The \(k\)-hop connected dominating set problem: approximation and hardness
- TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Algorithmic graph theory and perfect graphs
- Total domination in graphs
- Title not available (Why is that?)
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Paired-domination in graphs
- Domination critical graphs
- Edge Dominating Sets in Graphs
- \(k\)-tuple domination in graphs
- Incremental modular decomposition
- Title not available (Why is that?)
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- Perfect edge domination and efficient edge domination in graphs
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- An optimal greedy heuristic to color interval graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- Paired-domination of trees
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Paired domination on interval and circular-arc graphs
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Weighted domination of cocomparability graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Dynamic monopolies of constant size
- Algorithmic aspect of \(k\)-tuple domination in graphs.
- Title not available (Why is that?)
- An efficient algorithm to find next-to-shortest path on permutation graphs
- The \(k\)-tuple twin domination in generalized de Bruijn and Kautz networks
- Locating and paired-dominating sets in graphs
- Title not available (Why is that?)
- Total Domination Edge Critical Graphs with Maximum Diameter
- Topics on domination
- R -Domination in Graphs
- Paired-domination in inflated graphs
- THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
- Minimum 2-tuple dominating set of an interval graph
- Total Domination and Irredundance in Weighted Interval Graphs
- An efficient algorithm to solve the distancek-domination problem on permutation graphs
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- A linear time algorithm for optimal \(k\)-hop dominating set of a tree
- Hop domination in graphs. II
- Bounds on the hop domination number of a tree
- Breadth-first traversal of trees and integer sorting in parallel
- On 2-step and hop dominating sets in graphs
- Title not available (Why is that?)
Cited In (4)
This page was built for publication: An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985488)
