Dominations in trapezoid graphs

DOI10.1016/0020-0190(94)00159-6zbMath0938.68925OpenAlexW2076261965WikidataQ127314252 ScholiaQ127314252MaRDI QIDQ1342259

Y. Daniel Liang

Publication date: 21 June 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00159-6

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ Parallel algorithms for the domination problems in trapezoid graphs ⋮ An efficient algorithm to solve the distancek-domination problem on permutation graphs ⋮ Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Computation of inverse 1-center location problem on the weighted trapezoid graphs ⋮ Connected domination and dominating clique in trapezoid graphs ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs

Cites Work

• Unnamed Item
• Trapezoid graphs and their coloring
• Dominating sets in perfect graphs
• Incorporating negative-weight vertices in certain vertex-search graph algorithms
• Domination on Cocomparability Graphs
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph