Finding a minimum independent dominating set in a permutation graph
1985, \textit{M. Farber} and \textit{J. M. Keil} published a paper with the title `Domination in permutation graphs' in J. Algorithms 6, 309-321 (1985; Zbl 0598.05056), where they studied the problem of finding a minimum independent dominating set in a permutation graph and where they presented an \(O(n^ 3)\)-time algorithm. The three authors of this paper study the same problem and succeed in giving an O(n \(log^ 2 n)\)-time algorithm by means of a linear time reduction from the problem of finding a minimum independent dominating set (MIDS) to the problem of computing a shortest maximal increasing subsequence (SMIS).
- An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- scientific article; zbMATH DE number 1222845
- A new approach for the domination problem on permutation graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Fast algorithms for the dominating set problem on permutation graphs
- An efficient algorithm for maxdominance, with applications
- Domination in permutation graphs
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Maintenance of configurations in the plane
- Some beautiful arguments using mathematical induction
- Some modified algorithms for Dijkstra's longest upsequence problem
- Finding minimum dominating cycles in permutation graphs
- An efficient algorithm for maxdominance, with applications
- The weighted maximum independent set problem in permutation graphs
- The complexity of domination problems in circle graphs
- A theorem on permutation graphs with applications
- On the feedback vertex set problem in permutation graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Coloring permutation graphs in parallel
- Fast algorithms for the dominating set problem on permutation graphs
- On-line algorithms for the dominating set problem
- Generate all maximal independent sets in permutation graphs
- An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
- A resource assignment problem on graphs
- A new approach for the domination problem on permutation graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- A tight bound on the number of mobile servers to guarantee transferability among dominating configurations
This page was built for publication: Finding a minimum independent dominating set in a permutation graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117255)
