Tree polytope on 2-trees
Copyright policy )Tree polytope on 2-trees
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.
- École Polytechnique Fédérale de Lausanne EPFL Switzerland
Combinatorial optimization, Steiner Tree problem, Special polytopes (linear programming, centrally symmetric, etc.), 2-tree graphs, Programming involving graphs or networks, Abstract computational complexity for mathematical programming problems
Combinatorial optimization, Steiner Tree problem, Special polytopes (linear programming, centrally symmetric, etc.), 2-tree graphs, Programming involving graphs or networks, Abstract computational complexity for mathematical programming problems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).23 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!