Tractable connected domination for restricted bipartite graphs (extended abstract)

Finding a minimum connected dominating set (connected domination) is known-complete for chordal bipartite graphs, but tractable for convex bipartite graphs. In this paper, connected domination is shown tractable for circular-and triad-convex bipartite graphs, by efficient reductions from these graphs to convex bipartite graphs. ? 2013 Springer-Verlag Berlin Heidelberg.EI