𝔖 Bobbio Scriptorium
✦   LIBER   ✦

From steiner centers to steiner medians

✍ Scribed by Ortrud R. Oellermann

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
457 KB
Volume
20
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The Steiner distance of set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S. For n ≥ 2, the Steiner n‐eccentricity e~n~(v) of a vertex v of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contain v. The Steiner n‐center of G is the subgraph induced by those vertices of G having minimum n‐eccentricity. The Steiner n‐distance of a vertex v of G is defined as magnified image. The Steiner n‐median of G is the subgraph of G induced by the vertices of G of minimum Steiner n‐distance. Known algorithms for finding the Steiner n‐centers and Steiner n‐medians of trees are used to show that the distance between the Steiner n‐centre and Steiner n‐median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n‐center to the Steiner n‐median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On Steiner centers and Steiner medians o
On Steiner centers and Steiner medians of graphs
✍ Oellermann, Ortrud R. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 Յ n Յ ͉V(G)

Solving Steiner tree problems in graphs
Solving Steiner tree problems in graphs to optimality
✍ Koch, T.; Martin, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 2 views

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nea

Cyclotomic Conditions Leading to New Ste
Cyclotomic Conditions Leading to New Steiner 2-Designs
✍ Marco Buratti 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 246 KB

We improve the constructions of S. Bagchi and B. Bagchi for Steiner 2-designs which are point-regular over the additive group of a Galois ring. As a consequence, we get new cyclotomic conditions leading to point-regular Steiner 2-designs with block size k ʦ {7, 9, 11, 13, 17}.

A novel approach to phylogenetic trees:
A novel approach to phylogenetic trees: d-Dimensional geometric Steiner trees
✍ M. Brazil; D.A. Thomas; B.K. Nielsen; P. Winter; C. Wulff-Nilsen; M. Zachariasen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

## Abstract We suggest a novel distance‐based method for the determination of phylogenetic trees. It is based on multidimensional scaling and Euclidean Steiner trees in high‐dimensional spaces. Preliminary computational experience shows that the use of Euclidean Steiner trees for finding phylogenet