Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight (v). A multicoloring of G is to assign each vertex v a set of (v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

一种新型的圈图绘制算法

提出了一种新型的圈图绘制算法,能对七种生物信息数据进行处理,并利用Perl程序设计语言给予实现。研究结果证明这种算法是行之有效的。     

Dynamic expression trees

We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include changing the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortestst-path in a series-parallel subgraph.Research supported in part by the National Science Foundation under Grant CCR-9007851, by the US Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225, and by Cadre Technologies, Inc.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

一个大规模股市图交互式可视化分析系统

随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。     

基于排列图的优化广播报文算法

文章就一种特殊的图——排列图的广播算法展开讨论。首先,给出了关于排列图的一些定义。根据排列图的定义,可以知道排列图的结构具有层次性。从这一点出发,作者得出一个把排列图分成一些子图,在子图中分别广播报文的递归算法。之后,作者考虑时间复杂度和报文复杂度,得出递归算法的两点改进。最后,给出了最后的广播算法。     

求解多段图问题的并行动态规划算法

多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。     

Routing on Metacyclic Graphs

［1］S. B. Akers, B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput,1989,38:555～566 ［2］F. F. Annexstein, M. Baumslag,A. L. Rosenberg. Group action graphs and parallel architectures. SIAM J. Comput, 1990,19     

用遗传算法画无向图

本文提出了一个新的画一般无向图的遗传算法.以前的无向图画图算法将顶点数较多且无弦的圈画成了凹多边形,为了克服这一缺点,本文的遗传算法设计了全新的变异算子--单点邻域变异,并在适应度函数中增加用于产生对称画法的分量,可将这种图画成凸多边形.新算法的优点是方法简单,易于实现,画出的图形美观,其灵活之处在于准则的权重可以改变.实验结果表明,在相同条件下,本文算法画出的图形要比标准遗传算法画出的图形美观.     

Disk Embeddings of Planar Graphs

Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of ${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve $\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$ but contains no other leaves of ${\FF}$. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces a connected subgraph of $G$.     

一个新的无向图画图算法

将一般无向图的画图问题转化为函数优化问题,用遗传算法求目标函数的最优解的近似值,从而得到无向图自动画图算法的一个一般框架.新方法的特点是:不同的画图算法的框架都一样,所不同的只是反映无向图画图问题的美观标准的目标函数.其优点在于,算法统一、方法简单、容易实现、便于修改,并且易于并行化,可以直接用来画非连通图.     

Maintaining Regular Properties Dynamically in k-Terminal Graphs

The t -topology tree data structure is developed for maintaining t -ary trees dynamically. Each of a certain set of tree operations is shown to take O(log n) time, where n is the number of vertices in the trees. The t -topology trees are used to maintain any given regular property on members of the family of k -terminal graphs under a variety of dynamic graph operations. Received February 1994; revised February 1995.     

带权图的均衡k划分

带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集S的顶点权值之和满足要求.此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明,当k分别取值为2,4,8时所提算法分别在86%,81%,68%的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60%以上.     

A 1-Local Asymptotic 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp. 526–536. Y. Zhang research was supported by European Regional Development Fund (ERDF). F.Y.L. Chin research was supported by Hong Kong RGC Grant HKU-7113/07E. H. Zhu research was supported by National Natural Science Fund (grant #60496321).     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

An Incremental Distributed Algorithm for Computing Biconnected Components in Dynamic Graphs

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst-case communication complexity of O(b+c) messages for an edge insertion and O(b'+c) messages for an edge removal, and a worst-case time complexity of O(c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and b' is the number of nodes in the biconnected component just before the deletion. The algorithm is presented in two stages. First, a serial algorithm is presented in which topology updates occur one at a time. Then, building on the serial algorithm, an algorithm is presented in which concurrent update requests are serialized within each connected component. The problem is motivated by the need to implement causal ordering of messages efficiently in a dynamically changing communication structure. Received January 1995; revised February 1997.     

Three-coloring planar graphs without short cycles

In this paper we prove that every planar graph without cycles of length 4, 6, 7 and 9 is 3-colorable.     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

A Heuristic Algorithm of Recognition of Isomorphism of Graphs

A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs.