×

zbMATH — the first resource for mathematics

Linear algorithms for the dominating cycle problems in series-parallel graphs, partial k-trees, and Halin graphs. (English) Zbl 0669.05050
Numerical mathematics and computing, Proc. 16th Conf., Winnipeg/Manit. 1986, Congr. Numerantium 57, 289-298 (1987).
In this paper the author confirms a reviewer’s conjecture and provides linear time algorithms for solving the dominating cycle problems for series-parallel graphs, partial k-trees and Halin graphs.
{Reviewer’s note: An algorithm for Halin graphs has been also presented in M. Skowrońska and M. M. Sysło, Dominating cycles in Halin graphs, Discrete Math. 1989.}
Reviewer: M.M.Sysło

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Keywords:
Halin graphs