graph has been widely used in modeling, specification, and design of parallel and distributed systems. Many parallel and distributed programs can be expressed as a collection of parallel functional modules whose relat...
详细信息
graph has been widely used in modeling, specification, and design of parallel and distributed systems. Many parallel and distributed programs can be expressed as a collection of parallel functional modules whose relationships can be defined by a graph. Often, the basic functions of communication and coordination of the parallel modules are expressed in terms of the underlying graph. Furthermore, parallel/distributed graph algorithms are used to realize various control functions. To facilitate the implementation of these algorithms, it is desirable to have an integrated approach that provides direct support for efficient operations on graphs. We have proposed a graph-oriented programming model, called GOP, which aims at providing high-level abstractions for configuring and programming cooperative parallel processes. GOP enables the programmer to configure the logical structure of a distributed program by using a logical graph and to write the program using communications and synchronization primitives based on the logical structure. In this paper, we describe the design and implementation of a portable run-time system for the GOP framework. The runtime system provides an interface with a library of programming primitives to the low-level facilities required to support graph-oriented communications and synchronization. The implementation is on top of the parallel virtual machine in a local area network of Sun workstations. We focus our discussion on the following four aspects: the software architecture, including the structure of runtime system and interfaces between user programs and the runtime kernel;graph representation;implementation of graph operations;and performance of the run-time in terms of the implementation of graph-oriented communications. (C) 2003 Elsevier Inc. All rights reserved.
We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u, v)-path is a shortest (u, v)-path amongst (u, v)-paths with length strictly greater than the length of the shortest (u, v)-...
详细信息
We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u, v)-path is a shortest (u, v)-path amongst (u, v)-paths with length strictly greater than the length of the shortest (u, v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem. (C) 2004 Published by Elsevier B.V.
An independent set in a graph G is a set I subset of or equal to V(G) such that the induced subgraph on I has no edges. A maximal independent set (MIS) is an independent set not properly contained in any other indepen...
详细信息
An independent set in a graph G is a set I subset of or equal to V(G) such that the induced subgraph on I has no edges. A maximal independent set (MIS) is an independent set not properly contained in any other independent set. We present a simple proof that an algorithm of Luby [SIAM J. Comput. 15 (1986) 1036] is an RNC algorithm for finding an MIS in a graph. Our proof can be easily derandomized, giving a corresponding NC algorithm. (C) 2004 Elsevier B.V. All rights reserved.
Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter, which includes, e.g., planar graphs. This characterization has been used as the basis for se...
详细信息
Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter, which includes, e.g., planar graphs. This characterization has been used as the basis for several (approximation) algorithms on such graphs (e.g., [2] and [5]-[8]). The proof of Eppstein is complicated. In this short paper we obtain the same characterization with a simple proof. In addition, the relation between treewidth and diameter is slightly better and explicit.
The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G wi...
详细信息
The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree. (C) 2003 Elsevier B.V. All rights reserved.
In this paper, we give an algorithm for the node-to-set disjoint paths problem in transposition graphs. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into...
详细信息
ISBN:
(纸本)1932415262
In this paper, we give an algorithm for the node-to-set disjoint paths problem in transposition graphs. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer experiment.
Given a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,E-T) of G, we study the problem of finding, for every node upsilon is an el...
详细信息
Given a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,E-T) of G, we study the problem of finding, for every node upsilon is an element of V, a set of replacement edges which can be used for constructing an MST of G-upsilon (i.e., the graph G deprived of upsilon and all its incident edges). We show that this problem can be solved on a pointer machine in O(***(m,n)) time and O.(m) space, where alpha is the functional inverse of Ackermann's function. Our solution improves over the previously best known O(min{***(n,n), m + n log n}) time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge e is an element ofE(T), a replacement edge which can be used for constructing an MST of G-e=(V,E\{e})). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.
MATRIX DOMINATION is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelizatio...
详细信息
MATRIX DOMINATION is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time O(n(3) + 1.959(k) k(5/2)). (C) 2004 Elsevier B.V. All rights reserved.
We study universal stability of directed and undirected graphs in the adversarial queuing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path befo...
详细信息
We study universal stability of directed and undirected graphs in the adversarial queuing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path before leaving the system. Restrictions on the allowed packet trajectory provide a way to analyze stability under different packet trajectories. We consider five packet trajectories, two for directed graphs and three for undirected graphs, and provide polynomial time algorithms for testing universal stability when considering each of them. In each case we obtain a different characterization of the universal stability property in terms of a set of forbidden subgraphs. Thus we show that variations of the allowed packet trajectory lead to nonequivalent characterizations. Using those characterizations we are also able to provide polynomial time algorithms for testing stability under the NTG-lis (Nearest To Go-Longest In System) protocol.
After [15], [31], [19], [8], [25], [5], minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimiza...
详细信息
After [15], [31], [19], [8], [25], [5], minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/maxflow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push-relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.
暂无评论