Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

Fault-Tolerant Hamiltonicity of Twisted Cubes

The twisted cube TQ_n, is derived by changing some connection of hypercube Q_n according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of V(TQ_n)∩E(TQ_n), we prove that TQ_n−F remains hamiltonian if |F|⩽n−2. Moreover, we prove that there exists a hamiltonian path in TQ_n−F joining any two vertices u, v in V(TQ_n)−F if |F|⩽n−3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQ_n is at most n−2 (n−3 respectively).     

交叉立方体内顶点不交叉路径长度的研究

Efe提出的交叉立方体（crossed cube）是超立方体（hypercube）的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论：在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径, 使得（1）最短路的长度=u和v之间的距离, （2）所有路中的最长路径长度≤u和v的距离＋4. 这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.     

Analysis of Shortest Paths and Subscriber Line Lengths in Telecommunication Access Networks

We consider random geometric models for telecommunication access networks and analyse their serving zones which can be given, for example, by a class of so-called Cox–Voronoi tessellations (CVTs). Such CVTs are constructed with respect to locations of network components, the nucleii of their induced cells, which are scattered randomly along lines induced by a Poisson line process. In particular, we consider two levels of network components and investigate these hierarchical models with respect to mean shortest path length and mean subscriber line length, respectively. We explain point-process techniques which allow for these characteristics to be computed without simulating the locations of lower-level components. We sustain our results by numerical examples which were obtained through Monte Carlo simulations, where we used simulation algorithms for typical Cox–Voronoi cells derived in a previous paper. Also, briefly, we discuss tests of correctness of the implemented algorithms. Finally, we present a short outlook to possible extensions concerning multi-level models and iterated random tessellations.     

Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces

Concept classes can canonically be represented by matrices with entries 1 and –1. We use the singular value decomposition of this matrix to determine the optimal margins of embeddings of the concept classes of singletons and of half intervals in homogeneous Euclidean half spaces. For these concept classes the singular value decomposition can be used to construct optimal embeddings and also to prove the corresponding best possible upper bounds on the margin. We show that the optimal margin for embedding n singletons is and that the optimal margin for half intervals over {1,...,n} is . For the upper bounds on the margins we generalize a bound by Forster (2001). We also determine the optimal margin of some concept classes defined by circulant matrices up to a small constant factor, and we discuss the concept classes of monomials to point out limitations of our approach.     

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes

It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Because of the similarity, our results can be immediately transfered to complete binary trees.     

A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths

We present an -time algorithm for the All Pairs Shortest Paths (APSP) problem for directed graphs with real edge lengths. This slightly improves previous algorithms for the problem obtained by Fredman, Dobosiewicz, Han, and Takaoka.     

Visualization of Isosurfaces with Parametric Cubes

To render images from volume datasets, an interpolation method also called reconstruction is needed. The level of details of the resultant image closely depends on the filter used for reconstruction. We propose here a new filter producing C ¹ continue surfaces. The provided image quality is better than current high-quality algorithms, like splatting or trilinear raycasting, where tiny details are often eliminated. In contrast with other studied high quality filters that are practically unusable, our algorithm has been implemented interactively on a modest platform thanks to an efficient implementation using parametric cubes. We also demonstrate the interest of a min-max octree in the visualization of isosurfaces interactively thresholded.     

注水法求解迷宫最优路径

根据灌溉系统的工作原理,提出注水法算法应用于求解迷宫最优路径问题.设定迷宫为一个灌溉系统,水从迷宫的入口注入,通过迷宫的通路水从迷宫的出口流出.从入口注入的水沿通路流向各个方向,在通路的各个位置记忆水流到达的时间.当迷宫出口有水流到达时,从出口到入口根据记录在通路上的时间逐步减小的原则逆向寻找入口就可找到迷宫的所有最优路径.该算法的空间复杂度和时间复杂度同迷宫的规模成线性关系.实验结果显示该算法是一种求解迷宫问题的有效算法.     

Optimal Pair of Minimal Paths Under Both Time and Budget Constraints

The quickest path (QP) problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. Two attributes are involved, namely, the capacity and the lead time. The capacity of each arc is assumed to be deterministic. However, in many real-life flow networks such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We modify the QP problem to a stochastic case. The new problem is to evaluate the probability that d units of data can be sent from the source to the sink under both time T and budget B constraints. Such a probability is named the system reliability. In particular, the data can be transmitted through two disjoint minimal paths (MPs) simultaneously. A simple algorithm is proposed to generate all (d, T, B)-QPs, and the system reliability can subsequently be computed. The optimal pair of MPs with highest system reliability could further be obtained.     

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).     

VA + Embeddings STAR: A State-of-the-Art Report on the Use of Embeddings in Visual Analytics

Over the past years, an increasing number of publications in information visualization, especially within the field of visual analytics, have mentioned the term “embedding” when describing the computational approach. Within this context, embeddings are usually (relatively) low-dimensional, distributed representations of various data types (such as texts or graphs), and since they have proven to be extremely useful for a variety of data analysis tasks across various disciplines and fields, they have become widely used. Existing visualization approaches aim to either support exploration and interpretation of the embedding space through visual representation and interaction, or aim to use embeddings as part of the computational pipeline for addressing downstream analytical tasks. To the best of our knowledge, this is the first survey that takes a detailed look at embedding methods through the lens of visual analytics, and the purpose of our survey article is to provide a systematic overview of the state of the art within the emerging field of embedding visualization. We design a categorization scheme for our approach, analyze the current research frontier based on peer-reviewed publications, and discuss existing trends, challenges, and potential research directions for using embeddings in the context of visual analytics. Furthermore, we provide an interactive survey browser for the collected and categorized survey data, which currently includes 122 entries that appeared between 2007 and 2023.     

Optimal Velocity Planning of Wheeled Mobile Robots on Specific Paths in Static and Dynamic Environments

This paper deals with optimal temporal‐planning of wheeled mobile robots (WMRs) when navigating on predefined spatial paths. A method is proposed to generate a time‐optimal velocity profile for any spatial path in static environments or when mobile obstacles are present. The method generates a feasible trajectory to be tracked by fully exploiting velocity, acceleration and deceleration boundaries of the WMR, and by ensuring the continuity of the velocity and acceleration functions. As an additional benefit for the tracking process the jerk is also bounded. The algorithm is not time consuming, since it mostly uses closed mathematical expressions, nonetheless iteration strategies are presented to solve specific situations. However, such situations are not expected to occur when the spatial paths are planned as smooth curves. The success of the algorithm was tested by experimental and simulation results on the WMR “RAM.” © 2003 Wiley Periodicals, Inc.     

An Efficient Motion Strategy to Compute Expected-Time Locally Optimal Continuous Search Paths in Known Environments

In this paper we address the problem of finding time-optimal search paths in known environments. In particular, we address the problem of searching a known environment for an object whose unknown location is characterized by a known probability density function (PDF). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the PDF for the object's location. The optimization problem we consider is that of finding the path that minimizes the expected value of the time required to find the object. As the complexity of the problem precludes finding an exact optimal solution, we propose a two-level, heuristic approach to finding the optimal search path. At the top level, we use a decomposition of the workspace based on critical curves to impose a qualitative structure on the solution trajectory. At the lower level, individual segments of this trajectory are refined using local numerical optimization methods. We have implemented the algorithm and present simulation results for the particular case when the object's location is specified by the uniform PDF.     

OLAP查询多维数据的新模型

针对目前现有的OLAP查询机制,讨论了一种新的模型——统计树。这种模型可以应用到OLAP中,并能够有效提高OLAP查询多维数据的速度。     

Towards the Web of Embeddings: Integrating multiple knowledge graph embedding spaces with FedCoder

The Semantic Web is distributed yet interoperable: Distributed since resources are created and published by a variety of producers, tailored to their specific needs and knowledge; Interoperable as entities are linked across resources, allowing to use resources from different providers in concord. Complementary to the explicit usage of Semantic Web resources, embedding methods made them applicable to machine learning tasks. Subsequently, embedding models for numerous tasks and structures have been developed, and embedding spaces for various resources have been published. The ecosystem of embedding spaces is distributed but not interoperable: Entity embeddings are not readily comparable across different spaces. To parallel the Web of Data with a Web of Embeddings, we must thus integrate available embedding spaces into a uniform space.Current integration approaches are limited to two spaces and presume that both of them were embedded with the same method — both assumptions are unlikely to hold in the context of a Web of Embeddings. In this paper, we present FedCoder— an approach that integrates multiple embedding spaces via a latent space. We assert that linked entities have a similar representation in the latent space so that entities become comparable across embedding spaces. FedCoder employs an autoencoder to learn this latent space from linked as well as non-linked entities.Our experiments show that FedCoder substantially outperforms state-of-the-art approaches when faced with different embedding models, that it scales better than previous methods in the number of embedding spaces, and that it improves with more graphs being integrated whilst performing comparably with current approaches that assumed joint learning of the embeddings and were, usually, limited to two sources. Our results demonstrate that FedCoder is well adapted to integrate the distributed, diverse, and large ecosystem of embeddings spaces into an interoperable Web of Embeddings.     

深度学习中汉语字向量和词向量结合方式探究

该文旨在探究深度学习中汉语字向量和词向量的有效结合方式。我们在以词作为基础语义单元和以字作为基础语义单元这两个方向进行探究,实验了字、词信息多种浅层结合方式和深层结合方式。为了验证该文提出的结合方式的有效性,我们改进了一种compare-aggregate模型,并在基于文档的问答系统上进行了实验。实验结果表明,有效的汉语字向量和词向量的结合方式超越了单独的字向量和词向量,提升了基于文档的问答系统的性能,使其结果与目前最好的结果可媲美。