ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Algorithms on Graphs with Small Dominating Targets.

Divesh Aggarwal and Chandan Dubey and Shashank Mehta

A dominating target of a graph G=(V,E) is a set of vertices T s.t. for all W ⊆ V, if T ⊆ W and induced subgraph on W is connected, then W is a dominating set of G. The size of the smallest dominating target is called dominating target number of the graph, dt(G). We provide polynomial time algorithms for minimum connected dominating set, Steiner set, and Steiner connected dominating set in dominating-pair graphs (i.e., dt(G)=2). We also give approximation algorithm for minimum connected dominating set with performance ratio 2 on graphs with small dominating targets. This is a significant improvement on appx ≤d(opt + 2) given by Fomin [2004] on graphs with small d-octopus.