An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

DOI10.1016/S0166-218X(98)00145-0zbMath1052.90095OpenAlexW2103589346MaRDI QIDQ1566569

H. S. Chao, Fang-Rong Hsu, Richard Chia-Tung Lee

Publication date: 30 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00145-0

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

Vizing bound for the chromatic number on some graph classes ⋮ Acyclic domination on bipartite permutation graphs ⋮ An efficient algorithm to solve the distancek-domination problem on permutation graphs ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Permutation bigraphs and interval containments ⋮ Succinct permutation graphs ⋮ On the domination number of permutation graphs and an application to strong fixed points ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Domination problems on P₅-free graphs ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• A new approach for the domination problem on permutation graphs
• On domination problems for permutation and other graphs
• An efficient algorithm for maxdominance, with applications
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• Connected domination and Steiner set on weighted permutation graphs
• Fast algorithms for the dominating set problem on permutation graphs
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• Some Efficient Algorithms for Permutation Graphs
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph

This page was built for publication: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs