Publication
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
Related concepts (33)
Multitree
In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset).
Convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact.
Directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.
Euclidean minimum spanning tree
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
Arc welding
Arc welding is a welding process that is used to join metal to metal by using electricity to create enough heat to melt metal, and the melted metals, when cool, result in a binding of the metals. It is a type of welding that uses a welding power supply to create an electric arc between a metal stick ("electrode") and the base material to melt the metals at the point of contact. Arc welding power supplies can deliver either direct (DC) or alternating (AC) current to the work, while consumable or non-consumable electrodes are used.
Gas tungsten arc welding
Gas tungsten arc welding (GTAW), also known as tungsten inert gas (TIG) welding, is an arc welding process that uses a non-consumable tungsten electrode to produce the weld. The weld area and electrode are protected from oxidation or other atmospheric contamination by an inert shielding gas (argon or helium). A filler metal is normally used, though some welds, known as autogenous welds, or fusion welds do not require it. When helium is used, this is known as heliarc welding.
Partial cube
In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels.
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.
Pathwidth
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition.
Plasma arc welding
Plasma arc welding (PAW) is an arc welding process similar to gas tungsten arc welding (GTAW). The electric arc is formed between an electrode (which is usually but not always made of sintered tungsten) and the workpiece. The key difference from GTAW is that in PAW, the electrode is positioned within the body of the torch, so the plasma arc is separated from the shielding gas envelope. The plasma is then forced through a fine-bore copper nozzle which constricts the arc and the plasma exits the orifice at high velocities (approaching the speed of sound) and a temperature approaching 28,000 °C (50,000 °F) or higher.