Given a graph G, the Minimum Dominating Trail Set (MDTS) problem consists in finding a minimum cardinality collection of pairwise edge-disjoint trails such that each edge of G has at least one endvertex on some trail....
详细信息
Given an undirected, 2-edge-connected, and real weighted graph G, with n vertices and m edges, and given a spanning tree T of G, the 2-edge-connectivity augmentation problem with respect to G and T consists of finding...
详细信息
ISBN:
(纸本)3540241310
Given an undirected, 2-edge-connected, and real weighted graph G, with n vertices and m edges, and given a spanning tree T of G, the 2-edge-connectivity augmentation problem with respect to G and T consists of finding a minimum-weight set of edges of G whose addition to T makes it 2-edge-connected. While the general problem is NP-hard, in this paper we prove that it becomes polynomial time solvable if T can be rooted in such a way that a prescribed topological condition with respect to G is satisfied. In such a case, we provide an O(n(m + h + delta(3))) time algorithm for solving the problem, where h and delta are the height and the maximum degree of T, respectively. A faster version of our algorithm can be used for 2-edge connecting a spider tree, that is a tree with at most one vertex of degree greater than two. This finds application in strengthening the reliability of optical networks.
We describe JGAP, a web-based platform for designing and implementing Java-coded graph algorithms. The platform contains a library of common data structures for implementing graph algorithms, features a 'plug-and-...
详细信息
We describe JGAP, a web-based platform for designing and implementing Java-coded graph algorithms. The platform contains a library of common data structures for implementing graph algorithms, features a 'plug-and-play' modular design for adding new algorithm modules, and includes a performance meter to measure the execution time of implemented algorithms. JGAP is also equipped with a graph editor to generate and modify graphs to have specific properties. JGAP's graphic user interface further allows users to compose, in a functional way, computation, sequences from existing algorithm modules so that output from an algorithm is used as input for another algorithm. Hence, JGAP can be viewed as a visual graph calculator for helping experiment with and teach graph algorithm design. Copyright (C) 2001 John Wiley & Sons, Ltd.
Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors ...
详细信息
ISBN:
(纸本)9781581138313
Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved - that they seem to share some deep structure. We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or "matter", while reference counting operates on dead objects, or "anti-matter". For every operation performed by the tracing collector, there is a precisely corresponding anti-operation performed by the reference counting *** this framework, we show that all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of tracing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the expected properties of the target application.
In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until...
详细信息
In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iterations which is an upper bound of thickness for an input graph G=(V, E). We show that the performance ratio of the greedy algorithm is Omega(log \V\). (C) 2002 Elsevier Science B.V. All rights reserved.
We present an efficient and scalable coarse grained multicomputer (CGM) coloring algorithm that colors a graph G with at most Delta + 1 colors where A is the maximum degree in G. This algorithm is given in two variant...
详细信息
We present an efficient and scalable coarse grained multicomputer (CGM) coloring algorithm that colors a graph G with at most Delta + 1 colors where A is the maximum degree in G. This algorithm is given in two variants: randomized and deterministic. We show that on a p-processor CGM model the proposed algorithms require a parallel time of O(\G\/p) and a total work and overall communication cost of O(\G\). These bounds correspond to the average case for the randomized version and to the worst case for the deterministic variant. (C) 2003 Elsevier B.V. All rights reserved.
A k-chordalisation of a graph G = (V, E) is a graph H = (V, F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V, E...
详细信息
A k-chordalisation of a graph G = (V, E) is a graph H = (V, F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V, E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G'. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.
We present an efficient and scalable coarse grained multicomputer (CGM) coloring algorithm that colors a graph G with at most Delta + 1 colors where A is the maximum degree in G. This algorithm is given in two variant...
详细信息
We present an efficient and scalable coarse grained multicomputer (CGM) coloring algorithm that colors a graph G with at most Delta + 1 colors where A is the maximum degree in G. This algorithm is given in two variants: randomized and deterministic. We show that on a p-processor CGM model the proposed algorithms require a parallel time of O(\G\/p) and a total work and overall communication cost of O(\G\). These bounds correspond to the average case for the randomized version and to the worst case for the deterministic variant. (C) 2003 Elsevier B.V. All rights reserved.
The P-4 is the induced path with vertices a, b, c, d and edges ab, bc, cd. The chair (co-P, gem) has a fifth vertex adjacent to b (a and b, a, b, c and d, respectively). We give a complete structure description of pri...
详细信息
The P-4 is the induced path with vertices a, b, c, d and edges ab, bc, cd. The chair (co-P, gem) has a fifth vertex adjacent to b (a and b, a, b, c and d, respectively). We give a complete structure description of prime chair-, co-P- and gem-free graphs which implies bounded clique width for this graph class. It is known that this has some nice consequences;very roughly speaking, every problem expressible in a certain kind of Monadic Second Order Logic (quantifying only over vertex set predicates) can be solved efficiently for graphs of bounded clique width. In particular, we obtain linear time for the problems Vertex Cover, Maximum Weight Stable Set (MWS), Maximum Weight Clique, Steiner Tree, Domination and Maximum Induced Matching on chair-, co-P- and gem-free graphs and a slightly larger class of graphs. This drastically improves a recently published O(n(4)) time bound for Maximum Stable Set on butterfly-, chair-, co-P- and gem-free graphs. (C) 2003 Elsevier Science B.V. All rights reserved.
暂无评论