Normal Extensions Escape from the Class of Weighted Shifts on Directed Trees

A formally normal weighted shift on a directed tree is shown to be a bounded normal operator. The question of whether a normal extension of a subnormal weighted shift on a directed tree can be modeled as a weighted shift on some, possibly different, directed tree is answered.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

Algebraic connectivity of weighted trees under perturbation

We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree.     

On Weighted Depths in Random Binary Search Trees

Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133–141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.     

树的变形与代数连通度

本文利用瓶颈矩阵的Perron值和代数连通度的二次型形式,系统地研究了当迁移或改变分支(边、点)和变动一些边的权重时无向赋权树的代数连通度的变化规律,认为代数连通度可用来描述树的边及其权重的某种中心趋势性.引入广义树和广义特征点概念,将II型树转换成具有相同代数连通度的I型树,使得树的代数连通度的讨论只须限于I型树的研究即可.     

On the weighted trees with given degree sequence and positive weight set

We determine the (unique) weighted tree with the largest spectral radius with respect to the adjacency and Laplacian matrix in the set of all weighted trees with a given degree sequence and positive weight set. Moreover, we also derive the weighted trees with the largest spectral radius with respect to the matrices mentioned above in the sets of all weighted trees with a given maximum degree or pendant vertex number and so on.     

A Unifying Approach for Proving Hook-Length Formulas for Weighted Tree Families

We propose an expansion technique for weighted tree families, which unifies and extends recent results on hook-length formulas of trees obtained by Han [10], Chen et al. [3], and Yang [19]. Moreover, the approach presented is used to derive new hook-length formulas for tree families, where several hook-functions in the corresponding expansion formulas occur in a natural way. Furthermore we consider families of increasingly labelled trees and show close relations between hook-length formulas for such tree families and corresponding ones for weighted tree families.     

On the Laplacian spectral radius of weighted trees with a positive weight set

The spectrum of weighted graphs is often used to solve the problems in the design of networks and electronic circuits. We first give some perturbational results on the (signless) Laplacian spectral radius of weighted graphs when some weights of edges are modified; we then determine the weighted tree with the largest Laplacian spectral radius in the set of all weighted trees with a fixed number of pendant vertices and a positive weight set. Furthermore, we also derive the weighted trees with the largest Laplacian spectral radius in the set of all weighted trees with a fixed positive weight set and independence number, matching number or total independence number.     

The Ricci curvature of a weighted tree

An expression for the coarse Ricci curvature of a weighted tree with a random walk on the vertex set is obtained. As a corollary, it is shown that the structure of a binary tree can be reconstructed up to isomorphism from the matrix of pairwise Ricci curvatures of its vertices.     

On component-size bounded Steiner trees

A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.     

Weighted Shifts on Directed Semi-Trees: an Application to Creation Operators on Segal–Bargmann Spaces

We extend the notion of a weighted shift on a directed tree to the case of a more general graph which we call a directed semi-tree. Some basic properties of such operators are investigated. It is shown that a generalized creation operator on the Segal–Bargman space is unitarily isomorphic to a weighted shift on a directed semi-tree of a particular form.     

Generating the maximum spanning trees of a weighted graph

The present paper contains an efficient algorithm for generating all the maximum spanning trees of a weighted graph and a polynomial time algorithm for counting them. As known, the tree representations of an acylic hypergraph are exactly the maximum spanning trees of the weighted intersection graph of its edges. Therefore, they can be generated and counted by these algorithms.     

Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime,weighted tardiness and weighted earliness of jobs

The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. Branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm.     

直觉模糊模型检测在工程决策上的应用

将直觉模糊Kripke结构扩展到加权直觉模糊Kripke结构,将直觉模糊计算树逻辑诱导到加权直觉模糊计算树逻辑;研究在此之上的直觉模糊期望测度和多属性工程决策问题。用加权直觉模糊Kripke结构的权值自然地刻画了工程问题中的成本和收益,直觉模糊测度量化工程进展的不确定性,用加权直觉模糊计算树逻辑描述不确定性工程属性约束。给出了基于直觉模糊模型检测的多属性工程寻优算法,并讨论了算法的复杂度。     

An addendum to the hierarchical network design problem

The hierarchical network design problem is the problem to find a spanning tree of minimum total weight, when the edges of the path between two given nodes are weighted by an other cost function than the tree edges not on this path. We point out that a dynamic programming oriented heuristic can already be found in literature. Further we report on possible extensions and improvements.     

“Optimistic” weighted Shapley rules in minimum cost spanning tree problems

We introduce optimistic weighted Shapley rules in minimum cost spanning tree problems. We define them as the weighted Shapley values of the optimistic game v⁺ introduced in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., forthcoming. The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Available from: <http://webs.uvigo.es/gbergant/papers/cstShapley.pdf>]. We prove that they are obligation rules [Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121–134].     

Analytic structure of weighted shifts on directed trees

We show that a weighted shift on a directed tree is related to a multiplier algebra of coefficients of analytic functions. We use this relation to study spectral properties of the operator in question.     

Multicriteria decision analysis in a decision tree

The outcomes at the tips of a decision tree cannot always be represented by a single numerical value on a one-dimensional axis. In many decision problems they are multidimensional, and their performance is expressed in a mixture of verbal statements and physical or monetary values. We propose to use the scores of cardinal methods for multicriteria decision analysis in order to represent the relative performance of the outcomes. Thereafter, we evaluate the chance forks in the tree via the corresponding aggregation procedure: in the Multiplicative AHP via weighted geometric means of the scores and in SMART via weighted arithmetic means. The procedure is based on the idea that the numerical values of verbal quantifiers like somewhat more, more, … do not depend on what we compare, whether it is relative importance or relative likelihood.     

Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.