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

      0 references
      1984
      0 references
      Halin graph
      0 references
      set cover
      0 references
      independent face cover
      0 references
      outerplanar graph
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references