Displaying similar documents to “A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ”

A new relaxation in conic form for the euclidean Steiner problem in ℜ n

Marcia Fampa, Nelson Maculan (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in ℜ n . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ -optimal solution for this latter problem using interior-point algorithm.

Morphospace: Measurement, Modeling, Mathematics, and Meaning

N. Khiripet, R. Viruchpintu, J. Maneewattanapluk, J. Spangenberg, J.R. Jungck (2010)

Mathematical Modelling of Natural Phenomena

Similarity:

Artists have long recognized that trees are self-similar across enormous differences in magnitudes; i.e., they share a common fractal structure - a trunk subdivides into branches which subdivide into more branches which eventually terminate in leaves, flowers, fruits, etc. Artistid Lindenmayer (1971, 1975, 1989, 1990) invented a mathematics based on graph grammar rewriting systems to describe such iteratively branching structures; these were named in honor of him and are referred to...

The triangles method to build -trees from incomplete distance matrices

Alain Guénoche, Bruno Leclerc (2010)

RAIRO - Operations Research

Similarity:

A method to infer -trees (valued trees having as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2-3 distance values between the elements of , if they fulfill some explicit conditions. This construction is based on the mapping between -tree and a weighted generalized 2-tree spanning .

Tree inclusion problems

Patrick Cégielski, Irène Guessarian, Yuri Matiyasevich (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Given two trees (a target and a pattern ) and a natural number , consist in deciding whether occurs as an embedded subtree of and/or finding the number of size (at most) windows of which contain pattern as an embedded subtree. is an embedded subtree of if can be obtained by deleting some nodes from (if a node is deleted, all edges adjacent to are also deleted, and outgoing edges are replaced by edges going from the parent of (if it exists) to the children of ). Deciding...

Hopcroft's algorithm and tree-like automata

G. Castiglione, A. Restivo, M. Sciortino (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard...

Minimal 2-dominating sets in trees

Marcin Krzywkowski (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order in time 𝒪(1.3248). This implies that every tree has at most 1.3248 minimal 2-dominating sets. We also show that this bound is tight.