Skip to main content
profile image
Selected Works of Y. Daniel Liang
Article
Parallel Algorithms for Domination Problems in Trapezoid Graphs
Discrete Applied Mathematics (1997)
  • Y. Daniel Liang, Georgia Southern University
Link
Abstract
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(log2n) time on a EREW PRAM.
Keywords
  • Connected domination,
  • Domination,
  • Independent domination,
  • Parallel algorithm,
  • Trapezoid graph,
  • Total domination
Disciplines
Publication Date
May 2, 1997
DOI
https://doi.org/10.1016/S0166-218X(96)00052-2
Citation Information
Y. Daniel Liang. "Parallel Algorithms for Domination Problems in Trapezoid Graphs" Discrete Applied Mathematics Vol. 74 Iss. 3 (1997) p. 241 - 249
Available at: http://works.bepress.com/yong-daniel-liang/19/