×

Steiner trees, connected domination and strongly chordal graphs. (English) Zbl 0579.05050

Summary: We consider Steiner tree problems and connected dominating set problems for several classes of graphs. We give a polynomial algorithm and a min- max theorem for the cardinality Steiner problem in strongly chordal graphs and a polynomial algorithm for the weighted connected dominating set problem in series-parallel graphs. We establish simple direct transformations between Steiner problems and connected domination problems for several classes of graphs and establish related NP- completeness results.

MSC:

05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstee, J. Algorithms 5 pp 215– (1984)
[2] and , The graphical travelling salesman problem and some related integer polyhedra. Research Report no. 378, Laboratoire d’Informatique et de Mathématiques Appliquées de Grenoble (1983).
[3] Dirac, Abh. Math. Seminar Univ. Hamburg 25 pp 71– (1961)
[4] Duffin, J. Math. Anal. Appl. 10 pp 303– (1965)
[5] Farber, Discrete Math. 43 pp 173– (1983)
[6] and , Convexity in graphs and hypergraphs. Research Report CORR 83-46, University of Waterloo (1983).
[7] Garey, SIAM J. Appl. Math. 32 pp 826– (1977)
[8] and , Computers and Intractibility. W. H. Freeman, San Francisco (1979).
[9] and , Totally-balanced and greedy matrices (in press). · Zbl 0573.05041
[10] Reducibility among combinatorial problems. Complexity of Computer Computations, and (Eds.), Plenum, New York (1962), pp. 85–103.
[11] Kikuno, Discrete Appl. Math. 5 pp 299– (1983)
[12] On dual integrality, min-max equalities and algorithms in combinatorial linear programs. Ph. D. thesis, University of Waterloo (1982).
[13] and , Domination and irredundance in split graphs. Technical Report 430, Clemson University (1983).
[14] Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976). · Zbl 0413.90040
[15] and , NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, Clempon University (1983).
[16] and , A polynomial algorithm for a class of Steiner tree problems on graphs. Industrial and Systems Engineering Report Series J-82-5, Georgia Institute of Technology (1982).
[17] Rose, J. Math. Anal. Appl. 32 pp 597– (1970)
[18] Wald, Networks 13 pp 159– (1983)
[19] Steiner trees and strongly chordal graphs. M. Math, thesis, University of Waterloo (1983).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.