Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

DOI10.1016/j.dam.2003.04.004zbMath1043.05090OpenAlexW2084877920MaRDI QIDQ1827836

J. Mark Keil, Patrice Belleville

Publication date: 6 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.dam.2003.04.004

zbMATH Keywords

Dominating setComparability graphBounded tolerance graphTrapezoid graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ On the intersection of tolerance and cocomparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Tolerance graphs
• Clustering and domination in perfect graphs
• Trapezoid graphs and their coloring
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Fast algorithms for the dominating set problem on permutation graphs
• New Data Structures for Orthogonal Range Queries
• On testing isomorphism of permutation graphs
• On Finding the Maxima of a Set of Vectors
• Tolerance graphs, and orders
• Some Efficient Algorithms for Permutation Graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs

This page was built for publication: Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs