Fast algorithms for the dominating set problem on permutation graphs

DOI10.1007/BF01190158MaRDI QIDQ2366239zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 29 June 1993

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01190158

zbMATH Keywords

data structuresdominating set problemdynamic programmingpermutation graphs

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• 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 optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Domination in permutation graphs

Cites work

• Domination in permutation graphs
• Finding a minimum independent dominating set in a permutation graph
• On domination problems for permutation and other graphs
• Preserving order in a forest in less than logarithmic time and linear space

Cited in

(21)

• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• An efficient algorithm for maxdominance, with applications
• Finding a minimum independent dominating set in a permutation graph
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
• Improved bottleneck domination algorithms
• Graph classes with structured neighborhoods and algorithmic applications
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Domination in permutation graphs
• scientific article; zbMATH DE number 4049081 (Why is no real title available?)
• Graph classes with structured neighborhoods and algorithmic applications
• A fast algorithm for multiplying min-sum permutations
• scientific article; zbMATH DE number 1222845 (Why is no real title available?)
• scientific article; zbMATH DE number 1302187 (Why is no real title available?)
• Some Efficient Algorithms for Permutation Graphs
• Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
• An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• Approximation algorithms for double domination number of graphs
• The bend number of cocomparability graphs
• A new approach for the domination problem on permutation graphs

This page was built for publication: Fast algorithms for the dominating set problem on permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366239)