Tree polytope on 2-trees
type: Item
instance of: scholarly article
title: Tree polytope on 2-trees
zbMATH Open document ID: 0807.90118
DOI: 10.1007/BF01582065
published in: Mathematical Programming. Series A. Series B
publication date: 1994-05-05T00:00:00Z
review text: The class of 2-tree graphs is defined inductively as follows: start with a single edge and add nodes by joining them to the two endpoints of an existing edge. Many NP-complete problems on graphs are polynomial when restricted to this class of graphs. In particular, the Steiner Tree problem is linear time solvable on graphs in this class. It is this observation that motivates the authors main result: a linear characterization of the convex hull of the characteristic vectors of trees of 2-free graphs.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 52B12
zbMATH DE Number: 563259
zbMATH Keywords: 2-tree graphs
zbMATH Keywords: Steiner Tree problem
author: François Margot
author: A. Prodon
author: Thomas M. Liebling
reviewed by: Rakesh V. Vohra
MaRDI profile type: Publication
cites work: An integer linear programming approach to the steiner problem in graphs
cites work: Faster exact algorithms for steiner trees in planar networks
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: The steiner problem in graphs
cites work: Q3048571
cites work: Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
cites work: A faster approximation algorithm for the Steiner problem in graphs
cites work: Steiner trees with \(n\) terminals among \(n+1\) nodes
cites work: Fast heuristic algorithms for rectilinear Steiner trees
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
cites work: Generalized Steiner problem in outerplanar networks
cites work: A dual ascent approach for steiner tree problems on a directed graph
Recommended article: On trees of polygons
Recommended article: Trees in Polyhedral Graphs
Recommended article: The polyhedral tree complex
Recommended article: The 2-radius and 2-radiian problems on trees
Recommended article: A classification of plane and planar 2-trees
Recommended article: The 2-dimension of a Tree
Recommended article: Q5316378
Recommended article: Two-graphs and trees
Recommended article: On the (2,2)-domination number of trees
Recommended article: Trees whose 2-domination subdivision number is 2
description: scientific article; zbMATH DE number 563259