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

Arnborg, Stefan; Proskurowski, Andrzej

SIAM J. Algebraic Discrete Methods 7, 305-314 (1986).

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áň

MSC:

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

Keywords:

graph reduction; confluent reduction; k-tree; polynomial time algorithm; recognizing subgraphs; 3-trees; reliability of communication networks; complexity of queries in data base systems

Citations:

Zbl 0221.05057; Zbl 0529.68036

References:

[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