An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
A vertex set \(S\) is said to be a dominating set for an undirected graph \((V,E)\) if for every vertex \(i\) in \(V\setminus S\) there is a vertex \(j\) in \(S\) such that \((i,j)\) belongs to \(E,A\) permutation graph is an undirected graph constructed on a given permutation of the numbers \(1, \dots,n\). The paper deals with a minimum cardinality dominating set problem: for given a permutation graph find the dominating set \(S\) with the minimum number of vertices. The authors present the linear time algorithm for the problem which is based on dynamic programming approach. The paper, which is not easy to read, brings new result. The best previous \(O(n\log\log n)\) algorithm is described by \textit{K. H. Tsai} and \textit{W. L. Hsu} in [Algorithmica 9, 601--614 (1993; Zbl 0768.68063)].
- scientific article; zbMATH DE number 1222845
- An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
- An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- Fast algorithms for the dominating set problem on permutation graphs
- Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
- Finding a minimum independent dominating set in a permutation graph
- Finding minimum dominating cycles in permutation graphs
- An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
- Algorithm of acyclic dominating set problem on bipartite permutation graphs
- An iterated greedy algorithm for finding the minimum dominating set in graphs
- A new approach for the domination problem on permutation graphs
- An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- An efficient algorithm for maxdominance, with applications
- Connected domination and Steiner set on weighted permutation graphs
- Dominating sets in perfect graphs
- Domination in permutation graphs
- Fast algorithms for the dominating set problem on permutation graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On Comparability and Permutation Graphs
- On domination problems for permutation and other graphs
- Permutation graphs: Connected domination and Steiner trees
- Some Efficient Algorithms for Permutation Graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Finding minimum dominating cycles in permutation graphs
- Finding a minimum independent dominating set in a permutation graph
- An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
- Paired-domination problem on distance-hereditary graphs
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- On the domination number of permutation graphs and an application to strong fixed points
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Fast algorithms for the dominating set problem on permutation graphs
- Minimum 2-tuple dominating set of permutation graphs
- Vizing bound for the chromatic number on some graph classes
- Succinct permutation graphs
- Permutation bigraphs and interval containments
- scientific article; zbMATH DE number 1222845 (Why is no real title available?)
- Best and worst case permutations for random online domination of the path
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Approximating dominating set on intersection graphs of rectangles and L-frames
- An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
- Domination problems on \(P_{5}\)-free graphs
- Algorithm of acyclic dominating set problem on bipartite permutation 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
- -boundedness and related problems on graphs without long induced paths: a survey
- Minimum vertex-edge dominating set of permutation graphs
- Optimal distance labeling for permutation graphs
- Acyclic domination on bipartite permutation graphs
- First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
This page was built for publication: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1566569)
