An estimate of the objective function optimum for the network Steiner problem

Date

2016-03-01

Author

Kirzhner, V.
Volkovich, Z.
Ravve, E.
Weber, Gerhard Wilhelm

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

44
views

0
downloads

A complete weighted graph, G(X, Gamma, W), is considered. Let (X) over tilde subset of X be some subset of vertices and, by definition, a Steiner tree is any tree in the graph G such that the set of the tree vertices includes set (X) over tilde. The Steiner tree problem consists of constructing the minimum-length Steiner tree in graph G, for a given subset of vertices (X) over tilde The effectively computable estimate of the minimal Steiner tree is obtained in terms of the mean value and the variance over the set of all Steiner trees. It is shown that in the space of the lengths of the graph edges, there exist some regions where the obtained estimate is better than the minimal spanning tree-based one.

Subject Keywords

Spanning tree, Steiner tree, Steiner problem

URI

https://hdl.handle.net/11511/57437

Journal

ANNALS OF OPERATIONS RESEARCH

DOI

https://doi.org/10.1007/s10479-015-2068-1

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

An overview of trace based public key cryptography over finite fields Akyıldız, Ersan (2014-03-15) The Discrete Log Problem (DLP), that is computing x, given y = alpha(x) and (alpha) = G subset of F-q*, based Public Key Cryptosystem (PKC) have been studied since the late 1970's. Such development of PKC was possible because of the trapdoor function! : Z(l) -> G = (alpha) subset of F-q*, f (m) = alpha(m) is a group homomorphism. Due to this fact we have; Diffie Hellman (DH) type key exchange, EIGamal type message encryption, and Nyberg-Rueppel type digital signature protocols. The cryptosystems based on th...
A phase diagram for ammonium halides Yurtseven, Hasan Hamit; Tublek, A (Informa UK Limited, 1995-01-01) In this study we have developed a mean field model to obtain the phase diagrams for NH4Cl and NH4Br. The phase diagrams obtained from our macroscopic theory are in good agreement with those obtained experimentally.
AN OPTIMAL-CONTROL PROBLEM WITH NONLINEAR ELLIPTIC STATE-EQUATIONS Leblebicioğlu, Mehmet Kemal (Elsevier BV, 1992-02-01) In this article some of the results for optimal control of linear systems have been generalized to a nonlinear case. This is achieved by employing standard techniques of the nonlinear theory. After demonstrating the existence of optimal controls, finite element method is used to discretize the problem. The resulting finite dimensional problem is solved by a special algorithm. The theoretical discussions are completed by proving that approximate solutions are reduced to exact solutions as the element size te...
Numerical method for optimizing stirrer configurations Schafer, M; Karasözen, Bülent; Uludağ, Yusuf; YAPICI, KEREM; Uğur, Ömür (2005-12-15) A numerical approach for the numerical optimization of stirrer configurations is presented. The methodology is based on a parametrized grid generator, a flow solver, and a mathematical optimization tool, which are integrated into an automated procedure. The flow solver is based on the discretization of the Navier-Stokes equations by means of the finite-volume method for block-structured, boundary-fitted grids with multi-grid acceleration and parallelization by grid partitioning. The optimization tool is an ...
Factor graph based linear minimum mean square error equalization for wireless communications / Şen, Pınar; Yılmaz, Ali Özgür; Department of Electrical and Electronics Engineering (2014) In this work, we have studied on a reduced complexity factor graph based linear minimum mean square error (LMMSE) filter as an equalizer for different wireless communication problems. First, we introduce an efficient way of computing extrinsic bit log-likelihood ratio (LLR) values for the LMMSE estimation through the previously presented graph structure in the literature compatible with higher order alphabets. In addition, we propose to adapt this graph structure so that it has the ability of including the ...

Citation Formats

V. Kirzhner, Z. Volkovich, E. Ravve, and G. W. Weber, “An estimate of the objective function optimum for the network Steiner problem,” ANNALS OF OPERATIONS RESEARCH, pp. 315–328, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57437.