scientific article; zbMATH DE number 3873380

From MaRDI portal
Publication:3340898





[For the entire collection see Zbl 0536.00020.] A Halin graph H is a plane graph consisting of a tree with no vertices of degree two, whose leaves are connected by a cycle C (edge-disjoint with T) in the order they are embedded. The travelling salesman problem on Halin graphs can be solved by a polynomial time algorithm. 1. For e in C let \(C_ e\) be the interior face implied by e and let \(S_ e\) be the set of the non-leaf-vertices in \(C_ e\cdot\underline S=\{S_ e\mid e\in C\}\) is an interior plane tree family. Such families are characterized and it is shown that the problem of covering the interior vertices of T by a minimal weight partition \(\underline S'\subset\underline S\) (assuming a weight function \(y:\underline S\to R\)) is polynomially solvable. 2. For plane graphs \(G=(V,E)\) an independent face cover is a subset \(W\subset V\) where no two vertices of W belong to a common face and every face contains a vertex in W. 2-connected graphs that have such a cover are characterized.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3340898)