Parallel algorithms for the domination problems in trapezoid graphs

DOI10.1016/S0166-218X(96)00052-2zbMath0876.05088OpenAlexW1971467398MaRDI QIDQ1356505

Y. Daniel Liang

Publication date: 25 November 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

parallel algorithmspolynomial algorithmstrapezoid graphsNP-completeminimum weight dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Some parallel algorithms on interval graphs
• Trapezoid graphs and their coloring
• Parallel algorithms for the connected components and minimal spanning tree problems
• Incorporating negative-weight vertices in certain vertex-search graph algorithms
• Improved processor bounds for parallel algorithms for weighted directed graphs
• Dominations in trapezoid graphs
• The minimum weight dominating set problem for permutation graphs is in NC
• Domination on Cocomparability Graphs