No label defined (Q3340898)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3873380
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3873380 |
Statements
1984
0 references
Halin graph
0 references
set cover
0 references
independent face cover
0 references
outerplanar graph
0 references
0.8035520911216736
0 references
0.8029094338417053
0 references
[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.
0 references