共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
4.
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. 相似文献
5.
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
2
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. 相似文献
6.
随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。 相似文献
7.
马毅 《计算机工程与应用》2001,37(21):66-69
文章就一种特殊的图——排列图的广播算法展开讨论。首先,给出了关于排列图的一些定义。根据排列图的定义,可以知道排列图的结构具有层次性。从这一点出发,作者得出一个把排列图分成一些子图,在子图中分别广播报文的递归算法。之后,作者考虑时间复杂度和报文复杂度,得出递归算法的两点改进。最后,给出了最后的广播算法。 相似文献
8.
Wenjun Xiao 《计算机科学》2002,29(Z1):101-102
[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 相似文献
9.
多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。 相似文献
10.
11.
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$. 相似文献
12.
13.
G. N. Frederickson 《Algorithmica》1998,22(3):330-350
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. 相似文献
14.
带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集S的顶点权值之和满足要求.此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明,当k分别取值为2,4,8时所提算法分别在86%,81%,68%的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60%以上. 相似文献
15.
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). 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
In this paper we prove that every planar graph without cycles of length 4, 6, 7 and 9 is 3-colorable. 相似文献
19.
对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O(n^3),但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O(n*degree(n)),degree(n)为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。 相似文献
20.
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. 相似文献