网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

计算两类网络的可靠性的多项式时间算法

定义了两类有向网络——ORC-网络和IRC-网络,并且提出一个计算它们的根通信可靠性(网络的一个特定结点(根点)能与其余每个结点通信的概率)的多项式时间算法.对于ORC-网络和IRC-网络,该算法的时间复杂度分别是O(｜E｜)和O(｜V｜·｜E｜),这里,｜V｜,｜E｜分别表示网络所含结点和边的数量.     

公交网络下的一种费用限制最小时态路径查询索引

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△_max·|E|·（log|E|+△_max））,其中,|V|表示顶点数,|E|表示边数,△_max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素.     

基于贝叶斯疑似度的启发式故障定位算法

故障定位问题理论上已经证明为NP-Hard问题.为了降低计算复杂度,以概率加权的二分图作为故障传播模型,提出了一种基于贝叶斯疑似度的启发式故障定位算法(Bayesian suspected degree fault localization algorithm,简称BSD).引入贝叶斯疑似度,对所有故障仅计算一遍;同时采用增量覆盖方式,使算法具有较低的计算复杂度O(|F|×|S|).仿真实验结果表明,BSD算法具有较高的故障检测率和较低的故障误检率,即使在部分告警无法观察、告警丢失和虚假等情况下,算法依然具有较高的故障检测率.BSD算法具有多项式计算复杂度,可以满足大规模通信网故障定位的要求.     

一种融合节点先验信息的图表示学习方法

图表示学习是实现各类图挖掘任务的基础。现实当中的图数据,不仅包含复杂的网络结构,还包括多样化的节点信息。如何将网络结构和节点信息更加有效地融入图的表示学习中,是一个重要的问题。为了解决这一问题,本文基于深度学习提出了融合节点先验信息的图表示学习方法。该方法将节点特征作为先验知识,要求学习到的表示向量同时保持图数据中的网络结构相似性和节点特征相似性。该方法的时间复杂度为O（|V|）,其中|V|为图节点数量,表明该方法适用于大规模图数据分析。同时,在多个数据集上的实验结果表明,所提出的方法相比目前流行的几种基线方法,在分类任务上能够获得良好而稳定的优势。     

多跳中继无线网络资源复用的建模及算法设计

建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法ARRS(adaptive resource reuse scheduling),以提高中继网络资源利用率.由于ARRS算法的核心步骤涉及顶加权图G(V,E,W)的染色,是NP-hard问题,为此给出了求解最优资源复用约束的顶加权图染色的近似算法ARRS_Greedy.该算法被证明具有时间复杂度O(|V|²),近似比为?(Δ+1)/2?(Δ表示图G顶点度数的最大值).该近似比是紧的.仿真分析验证了近似算法ARRS_Greedy在应用中取得了与最优解非常接近的性能,证明了ARRS算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量.     

基于压缩的图的零漏包率割点求解算法

随着需求的增大,数据规模迅速增长。同样在图的应用方面,图的规模也呈爆炸性增长,这样,图上的相关操作也因为图的规模巨大而变得异常艰难,这就需要研究者们提出新的方法来减少图上操作的难度。割点的查询是图的一个重要操作,提出了一种新的基于压缩的割点求解算法,在压缩的图上迅速确定原图上是否存在割点,若存在割点则返回全部可能割点,不会漏掉任何一个割点。同时,由于任何图应用中都会存在图的维护,提出一种在压缩图上进行增量维护的算法,避免了重新的计算,经过一次压缩后,压缩图可以永久使用。     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

面向时序数据的矩阵分解

研究一类特殊的矩阵分解问题:对由多个对象在一组连续时间点上产生的数据构成的矩阵R,寻求把它近似地分解为两个低秩矩阵U和V的乘积,即R≈U^T×V.有为数众多的时间序列分析问题都可归结为所研究问题的求解,如金融数据矩阵的因子分析、缺失交通流数据的估计等.提出了该问题的概率图模型,进而由此导出了其约束优化模型,最终给出了模型的求解算法.在不同的数据集上进行实验验证了该模型的有效性.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

The complexity of comparability graph recognition and coloring

Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.     

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.     

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|²) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.     

Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs

A bipartite graph G=(U,W,E) with vertex set V=U∪W is convex if there exists an ordering of the vertices of W such that for each u∈U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.     

Piecemeal Graph Exploration by a Mobile Robot

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G=(V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E+V^1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E+V²) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure.”     

Routing with multiple quality-of-services constraints: An approximation perspective

Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality.     

A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem

Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|²) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.     

Pictures as Boolean Formulas

Both labellability and realizability problems of planar projections of polyhedra (i.e., pictures) are known to be NP-complete problems. This is true, even in the case of trihedral polyhedra, where exactly three faces meet at every vertex. In this paper, we examine pictures that are taken to be projections of trihedral polyhedra without holes, and contain the projections of all edges (hidden and visible) of a polyhedron. In other words, we examine pictures which represent the entire shape of a trihedral polyhedron without holes. Such a picture is a connected graph P=(V,E) with |E| edges and |V| nodes, each of degree 3 ( $|E| = \frac{3|V|}{2}$ ). We propose a mathematical scheme that constructs from the picture a Boolean formula Φ _P , which is a conjunction of clauses, each consisting of at most two literals. Based on the satisfiability of Φ _P , we show that both labellability and realizability problems can be solved efficiently in polynomial time. The category of pictures with hidden lines consists of the first category of pictures, where the labellability problem is solved in polynomial time, and, moreover, its solution implies the solution of the realizability problem in polynomial time too. Our approach may also prove useful in other applications of scene analysis.     

Two flow network simplification algorithms

Flow network simplification can reduce the size of the flow network and hence the amount of computation performed by flow algorithms. We present the first linear time algorithm for the undirected network case. We also give an O(|E|∗(|V|+|E|)) time algorithm for the directed case, an improvement over the previous best O(|V|+²|E|log|V|) time solution. Both of our algorithms are quite simple.