Characterization and recognition of partial 3-trees. (English) Zbl 0597.05027

The authors present a polynomial time algorithm for recognizing subgraphs of 3-trees and embedding them into full 3-trees. This is related to some practical questions about reliability of communication networks and about complexity of queries in data base systems. [For the definition of a k- tree see L. W. Beineke and R. E. Pippert, Mathematika 18, 141-151 (1971; Zbl 0221.05057), for an analogous result on 2-trees see J. Wald and C. J. Colbourn, Networks 13, 159-167 (1983; Zbl 0529.68036).]
Reviewer: J.Širáň


05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
90B25 Reliability, availability, maintenance, inspection in operations research
68P20 Information storage and retrieval of data
Full Text: DOI


[1] On the complexity of multivariable query evaluationFOA RapportC20292-D8National Defence Research InstituteStockholm, Sweden1979
[2] Characterization and recognition of partial k-treesTRITA-NA 8402Royal Institute of TechnologySweden1984
[3] Complexity of finding embeddings in a k-treeTRITA-NA 8407Royal Institute of TechnologySweden1984
[4] Beineke, L. W.; Pippert, R. E., Properties and characterizations of k-trees, Mathematika, 18, 141, (1971) · Zbl 0221.05057
[5] Duffin, R. J., Topology of series-parallel networks, J. Math. Anal. Appl., 10, 303, (1965) · Zbl 0128.37002
[6] Farley, ArthurM., Networks immune to isolated failures, Networks, 11, 255, (1981) · Zbl 0459.94036
[7] Farley, ArthurM.; Proskurowski, Andrzej, Networks immune to isolated line failures, Networks, 12, 393, (1982) · Zbl 0493.94020
[8] Huet, G.; Oppen, D.; Book, R., Equations and rewrite rules: a survey, Formal Languages: Perspective and Open Problems, (1980), Academic Press, New York
[9] Graph reducibilityProceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976)Utilitas Math.Winnipeg, Man.1976433-445. Congressus Numerantium, No. XVII
[10] The most reliable series-parallel networksTR 83-7Dept. Comp. Sci., Univ. Saskatchewan1983
[11] Rose, D., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, (1970) · Zbl 0216.02602
[12] Rose, D., On simple characterizations of k-trees, Discrete Math., 7, 317, (1974) · Zbl 0285.05128
[13] Rose, D.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, (1976) · Zbl 0353.65019
[14] Wald, JosephA.; Colbourn, CharlesJ., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159, (1983) · Zbl 0529.68036
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.