Domination in Convex Bipartite and Convex-round Graphs
Jørgen Bang‐Jensen, Jing Huang, Gary MacGillivray, Anders Yeo · 1999
A bipartite graph G = (X, Y ; E) is convex if there exists a linear enumeration L of the vertices of X such that the neighbours of each vertex of Y are consecutive in L. We show that the problems of finding a minimum dominating set and a minimum independent dominating set in an n-vertex convex bipartite graph are solvable in time O(n 2 ). This improves previous O(n 3 ) algorithms for these problems. Recently, a new class of graphs called convex-round graphs have been introduced by Bang-Jensen, Huang and Yeo. These are the graphs in which vertices can be circularly enumerated so that the neighbours of every vertex are consecutive in the enumeration. As a byproduct, we show that a minimum dominating set and a minimum independent dominating set in a convex-round graph can be computed in time O(n 3 ). Using a reduction to circular arc graphs, we show that a minimum total dominating set in a convex-round graph (with a given convex-round enumeration) can be computed in tim...