scientific article; zbMATH DE number 3873380
[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.
- Dominating cycles in Halin graphs
- Traveling salesman problem under categorization
- Multiobjective traveling salesperson problem on Halin graphs
- Persistency in the traveling salesman problem on Halin graphs
- Algorithms for the optimal Hamiltonian path in Halin graphs
- scientific article; zbMATH DE number 4155883 (Why is no real title available?)
- scientific article; zbMATH DE number 4045507 (Why is no real title available?)
- Outer-Facial Graphs and the Traveling Salesman Problem
- Constrained Steiner trees in Halin graphs
- scientific article; zbMATH DE number 1786153 (Why is no real title available?)
- The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
- Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
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)