Gomory‐Hu trees of infinite graphs with finite total weight

A well‐known theorem of Gomory and Hu states that if G is a finite graph with nonnegative weights on its edges, then there exists a tree T (now called a Gomory‐Hu tree) on such that for all there is an such that the two components of determine an optimal (minimal valued) cut between u an v in G. In this article, we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one cannot omit the condition of the finiteness of the total weight.     

On minimum bisection and related cut problems in trees and tree‐like graphs

Minimum bisection denotes the NP‐hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded‐degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies . Second, we generalize this to arbitrary graphs with a given tree decomposition  and give an upper bound on the minimum bisection width that depends on how close  is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.     

Recurrence and non‐ergodicity in generalized wind‐tree models

In this paper, we consider generalized wind‐tree models and ‐covers over compact translation surfaces. Under suitable hypothesis, we prove the recurrence of the linear flow in a generic direction and the non‐ergodicity of Lebesgue measure.     

Predicting ships' CO2 emissions using feature‐oriented methods

Shipping companies are forced by the current EU regulation to set up a system for monitoring, reporting, and verification of harmful emissions from their fleet. In this regulatory background, data collected from onboard sensors can be utilized to assess the ship's operating conditions and quantify its CO₂ emission levels. The standard approach for analyzing such data sets is based on summarizing the measurements obtained during a given voyage by the average value. However, this compression step may lead to significant information loss since most variables present a dynamic profile that is not well approximated by the average value only. Therefore, in this work, we test two feature‐oriented methods that are able to extract additional features, namely, profile‐driven features (PdF) and statistical pattern analysis (SPA). A real data set from a Ro‐Pax ship is then considered to test the selected methods. The data set is segregated according to the voyage distance into short, medium, and long routes. Both PdF and SPA are compared with the standard approach, and the results demonstrate the benefits of employing more systematic and informative feature‐oriented methods. For the short route, no method is able to predict CO₂ emissions in a satisfactory way, whereas for the medium and long routes, regression models built using features obtained from both PdF and SPA improve their prediction performance. In particular, for the long route, the standard approach failed to provide reasonably good predictions.     

基于模式约束的XML数据存储和索引技术

对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.现有的索引和存储策略,大部分以丢失结构信息为代价,不利于结构查询和更新.XMLSchema作为描述XML文档结构信息的标准,对文档和查询路径进行有效性验证提供保证,基于此提出了一种基于XMLmSchema模式约束的XML文档数据索引技术SBXI,用于文档数据存储和查询的导航,提高了存储和查询效率,具有较高的空间利用率和较低的索引维护代价,并支持含有多个谓词的复杂查询.     

系统发育树构建中用EM算法进行参数估计

系统发育学研究物种之间的进化关系,其核苷酸替代模型通常假设序列进化没有数据的缺损和删失,而现实中这个假设条件是很难满足的.针对这种事实,本文将运用EM算法对存在插入或缺失但序列长度假设不变的观测序列构建系统发育树进行参数估计,为含缺损数据序列构建良好的系统发育树作铺垫.重点在于运用EM算法做Jukes-Cantor模型、Kimura模型下含缺损数据的DNA序列构建有根树或无根树最佳分枝长度等的参数估计.     

树依谱矩的排序

首先给出了图的四种变换,得到其对任意图的谱矩的影响规律,并且利用图的这四种变换给出了树依谱矩序列s4的字典序排在前三位和后三位的图及其特征。     

Sovereign debt crisis in the European Union: A minimum spanning tree approach

In the wake of the financial crisis, sovereign debt crisis has emerged and is severely affecting some countries in the European Union, threatening the viability of the euro and even the EU itself. This paper applies recent developments in econophysics, in particular the minimum spanning tree approach and the associate hierarchical tree, to analyze the asynchronization between the four most affected countries and other resilient countries in the euro area. For this purpose, daily government bond yield rates are used, covering the period from April 2007 to October 2010, thus including yield rates before, during and after the financial crises. The results show an increasing separation of the two groups of euro countries with the deepening of the government bond crisis.     

Distances in evidence theory: Comprehensive survey and generalizations

The purpose of the present work is to survey the dissimilarity measures defined so far in the mathematical framework of evidence theory, and to propose a classification of these measures based on their formal properties. This research is motivated by the fact that while dissimilarity measures have been widely studied and surveyed in the fields of probability theory and fuzzy set theory, no comprehensive survey is yet available for evidence theory. The main results presented herein include a synthesis of the properties of the measures defined so far in the scientific literature; the generalizations proposed naturally lead to additions to the body of the previously known measures, leading to the definition of numerous new measures. Building on this analysis, we have highlighted the fact that Dempster’s conflict cannot be considered as a genuine dissimilarity measure between two belief functions and have proposed an alternative based on a cosine function. Other original results include the justification of the use of two-dimensional indexes as (cosine; distance) couples and a general formulation for this class of new indexes. We base our exposition on a geometrical interpretation of evidence theory and show that most of the dissimilarity measures so far published are based on inner products, in some cases degenerated. Experimental results based on Monte Carlo simulations illustrate interesting relationships between existing measures.     

Equiseparability on terminal Wiener index

The aim of this work is to explore the properties of the terminal Wiener index, which was recently proposed by Gutman et al. (2004) [3], and to show the fact that there exist pairs of trees and chemical trees which cannot be distinguished by using it. We give some general methods for constructing equiseparable pairs and compare the methods with the case for the Wiener index. More specifically, we show that the terminal Wiener index is degenerate to some extent.