Abstract
In this paper we consider the relation of homogeneous sets (sometimes called modules) to the domination problems r-dominating clique and connected r-dominating set by investigating homogeneous extensions of graphs.
At first, we show that homogeneous extensions of a hereditary graph class \(\mathcal{G}\)can be recognized nearly as efficiently as the graphs of \(\mathcal{G}\), itself. The algorithm is based on modular decomposition.
In the main part of this work we show, that efficient algorithms solving the r-dominating clique and the connected r-dominating set problem (and thus the Steiner tree problem) on a hereditary graph class \(\mathcal{G}\)lead to efficient algorithms on their homogeneous extensions.
Applying these results to homogeneous extensions of trees we get efficient algorithms solving these problems in linear sequential and polylogarithmic parallel time using a linear number of processors.
This work is supported by the German Research Community DFG.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Abrahamson, N. Dadoun, D.G. Kirkpatrick and T. Przytycka, A simple parallel tree contraction algorithm, J. Algorithms 10 (1989), 287–302.
A. Brandstädt, Special graph classes — a survey, Technical Report Gerhard-Mercator-Universität — Gesamthochschule Duisburg SM-DU-199, 1991.
A. Brandstädt, V.D. Chepoi and F.F. Dragan, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Technical Report Gerhard-Mercator-Universität — Gesamthochschule Duisburg SM-DU-244, 1994.
A. Brandstädt, F.F. Dragan, V.D. Chepoi and V.I. Voloshin, Dually chordal graphs, Technical Report Gerhard-Mercator-Universität — Gesamthochschule Duisburg SM-DU-225, 1993; extended abstract in Proceedings of WG'93, Springer, Lecture Notes in Computer Science 790, 237–251.
G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM J. Algebraic and Discrete Methods, 5 (1984), 332–345.
A. Cournier and M. Habib, A simple linear algorithm to build modular decomposition trees, Technical Report LIRMM 94-063, Montpellier 1994.
E. Dahlhaus, Efficient parallel modular decomposition, Proceedings of WG'95, Springer, Lecture Notes in Computer Science 1017, 290–302.
A. D'Atri and M. Moscarini, Distance-hereditary graphs, Steiner trees and connected domination, SIAM J. Comp. 17 (1988), 521–538.
A. D'Atri, M. Moscarini and A. Sassano, The Steiner tree problem and homogeneous sets, Proceedings of MFCS'88, Springer, Lecture Notes in Computer Science 324, 249–261.
F.F. Dragan and F. Nicolai, r-dominating problems in homogeneously orderable graphs, Technical Report Gerhard-Mercator-Universität — Gesamthochschule Duisburg SM-DU-275, 1995, extended abstract in Proceedings of FCT'95, Springer, Lecture Notes in Computer Science 965, 201–210.
A. Gibbons and W. Rytter, Efficient parallel algorithms, Cambridge University Press, 1988.
X. He, Efficient parallel algorithms for solving some tree problems, in ‘24th Allerton Conference on Communication, Control and Computing', 1986, 777–786.
Y. He and Y. Yesha, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Algohthmica (1990), 129–145.
R. McConnell and J. Spinrad, Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs, Fifth Annual ACM-SIAM Symposium of Discrete Algorithms (1994), 536–545.
F. Nicolai and T. Szymczak, r-Domination problems on trees and their homogeneous extensions, Technical Report Gerhard-Mercator-Universität — Gesamthochschule Duisburg SM-DU-309, 1995.
F. Nicolai and T. Szymczak, Homogeneous Sets and Domination — A Linear Time Algorithm for Distance-Hereditary Graphs, Manuscript 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nicolai, F., Szymczak, T. (1997). Homogeneous sets and domination problems. In: d'Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds) Graph-Theoretic Concepts in Computer Science. WG 1996. Lecture Notes in Computer Science, vol 1197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62559-3_26
Download citation
DOI: https://doi.org/10.1007/3-540-62559-3_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62559-9
Online ISBN: 978-3-540-68072-7
eBook Packages: Springer Book Archive