几类特殊图中的最小最大多路割

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了(2-1/2k2)-近似算法,k表示终端的数目。     

传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。     

基于粘贴和2-臂DNA模型的层次聚类算法

为了充分利用DNA分子在生物计算中的高度并行性和强大的存储能力,将DNA计算引入层次聚类实现对数据集的全局搜索。提出了粘贴模型与2-臂DNA分子相结合的混合模型求解最近邻层次聚类的DNA算法。针对二维数据空间,算法首先基于最小生成树思想产生图的边的所有组合链;其次筛选含n-1条边的链,基于边附着顶点,并选择包含全部顶点的复合链;再将复合链末尾连接相应边的权值片段,电泳出最短链;最后通过荧光分析法读解,得到最终的聚类结果。与已有文献同类算法对比表明,该算法在保持多项式操作时间下,更充分考虑连接边的长度,并将读解步骤数限定为常数步。     

大规模分布数据的分阶段非线性聚类方法应用研究

提出一种能够有效处理大规模分布的数据聚类问题且简化计算复杂度的分阶段非线性聚类方法,该算法包含两个阶段：首先将数据划分为若干个球形分布的子类,采用K近邻图理论对原始数据计算顶点能量并提取顶点攻能量样本;再采用K近邻算法对该高能量样本做一个划分,从而得到一个考虑高能量样本的粗划分同时估计出聚类的个数,最后,综合两次聚类结果整理得到最终聚类结果。该方法的主要优点是可以用来处理复杂聚类问题,算法较为稳定,并且在保持聚类正确率的同时,降低了大规模分布数据为相似性度量的计算代价。     

基于CBT的多源Steiner树构造算法

构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题,不可能在多项式时间求得其精确解,所以出现许多启发式算法：在可接受时间内,得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用,通过一定方法或规则,找出包含源端和所有目的端的一棵近似最优的多播树。很显然,它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进,以适应不断变化了的链路费用。     

一种求解多旅行商问题双层降解混合算法*

为了能快速近似求解多旅行商问题,提出了双层降解混合算法。首层降解根据问题空间展布特性,利用聚类技术将问题分解为若干子类问题,底层降解将子类问题转换为经典的旅行商问题,通过缩减子类问题初始状态下的边数量,使得子类问题求解难度得到再度降低,最终利用精确算法进行求解能够得到高质量优化解。对比实验表明双层降解混合算法具有计算时间短和求解质量高的优势,说明了新算法的有效性和高效性。     

无线网络中最小权虚拟骨干网连通部分的新方法

无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小。通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法。同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+ε)-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。     

复杂分布数据的二阶段聚类算法

提出了一种用于复杂分布数据的二阶段聚类算法(two-phase clustering,简称TPC),TPC包含两个阶段:首先将数据划分为若干个球形分布的子类,每一个子类用其聚类中心代表该类内的所有样本;然后利用可以处理复杂分布数据的流形进化聚类(manifold evolutionary clustering,简称MEC)对第1阶段得到的聚类中心进行类别划分;最后综合两次聚类结果整理得到最终聚类结果.该算法基于改进的K-均值算法和MEC算法.在进化聚类算法的基础上引入流形距离,使得算法能够胜任复杂分布的数据聚类问题.同时,算法降低了引入流形距离所带来的计算量.在分布各异的7个人工数据集和7个UCI数据集测试了二阶段聚类算法,并将其效果与遗传聚类算法、K均值算法和流形进化聚类算法做了比较.实验结果表明,无论对于简单或复杂、凸或非凸的数据,TPC都表现出良好的聚类性能,并且计算时间与MEC相比明显减少.     

欧式平面上瓶颈Steiner树问题的一个近似算法

近些年来，Steiner树问题在理论和应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面，该问题占有一定的中心地位。给定赋权连通图G=(V，E，W)及顶点子集S包含V(S中顶点称为terminals)，传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点，该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时，传统的Steiner树问题仍然是MAX—SNP Hard。     

改进的最优顶点覆盖贪心边近似算法

最优顶点覆盖问题是6个基本的NP完全问题之一，无法在多项式时间内得到最优解，除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时，证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。     

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This paper concerns a domination problem in graphs with parity constraints. The task is to find a subset of the vertices with minimum cost such that for every vertex the number of chosen vertices in its neighbourhood has a prespecified parity. This problem is known to be ${\mathcal NP}$ -hard for general graphs. A linear time algorithm was developed for series-parallel graphs and trees with unit cost and restricted to closed neighbourhoods. We present a linear time algorithm for the parity domination problem with open and closed neighbourhoods and arbitrary cost functions on graphs with bounded treewidth and distance-hereditary graphs.     

Resource Allocation in Bounded Degree Trees

We study the bandwidth allocation problem (bap) in bounded degree trees. In this problem we are given a tree and a set of connection requests. Each request consists of a path in the tree, a bandwidth requirement, and a weight. Our goal is to find a maximum weight subset S of requests such that, for every edge e, the total bandwidth of requests in S whose path contains e is at most 1. We also consider the storage allocation problem (sap), in which it is also required that every request in the solution is given the same contiguous portion of the resource in every edge in its path. We present a deterministic approximation algorithm for bap in bounded degree trees with ratio . Our algorithm is based on a novel application of the local ratio technique in which the available bandwidth is divided into narrow strips and requests with very small bandwidths are allocated in these strips. We also present a randomized (2+ε)-approximation algorithm for bap in bounded degree trees. The best previously known ratio for bap in general trees is 5. We present a reduction from sap to bap that works for instances where the tree is a line and the bandwidths are very small. It follows that there exists a deterministic 2.582-approximation algorithm and a randomized (2+ε)-approximation algorithm for sap in the line. The best previously known ratio for this problem is 7. A preliminary version of this paper was presented at the 14th Annual European Symposium on Algorithms (ESA), 2006.     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees

We consider the problem of updating a single-source shortest path in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log n) amortized time per vertex update, where a vertex is considered updated if it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O( log n) amortized time per vertex update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6], require simple data structures that are really suitable for a practical and straightforward implementation. Received January 1995; revised February 1997.     

Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem

The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into s stacks of size h that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem.In the paper, we show that the PDTC problem can be solved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when h≥6 is a fixed constant, but s is unbounded.     

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph’s feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters “feedback vertex set number” and “number of vertices to delete”. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the “number of vertices to delete”. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter “feedback edge set number”. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter “vertex cover number and number of vertices to delete”, implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.     

Cluster editing problem for points on the real line: A polynomial time algorithm

In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs.     

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem

Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V ₁ , . . ., V _k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them. Received February 13, 1998; revised July 8, 1998.     

Algorithms for Graphs Embeddable with Few Crossings per Edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge.