Parallel algorithms for the domination problems in trapezoid graphs

✍ Scribed by Y.Daniel Liang

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 608 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00052-2

✦ Synopsis

Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O(log'n) time on a EREW PRAM. The number of processors required is O(max{n3/log2 n,n2.376}) for th e independent domination problem, and O(max {nm2/log2 n, m2.376 }) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.