Algorithms on Graphs with Small Dominating Targets.

Divesh Aggarwal, Chandan Dubey, and Shashank Mehta

Algorithms and Computation, 17th International Symposium, ISAAC 2006, Lecture Notes in Computer Science, Springer, vol. 4288, pp. 141-152, Dec 2006.

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 et.al. [2004] on graphs with small d-octopus.

BibTeX Citation

@inproceedings{AgDuMe06,
    author       = {Divesh Aggarwal and Chandan Dubey and Shashank Mehta},
    title        = {Algorithms on Graphs with Small Dominating Targets.},
    editor       = {Tetsuo Asano},
    booktitle    = {Algorithms and Computation, 17th International Symposium, ISAAC 2006},
    pages        = 141-152,
    series       = {Lecture Notes in Computer Science},
    volume       = 4288,
    year         = 2006,
    month        = 12,
    publisher    = {Springer},
}