We present results related to satisfying shortest path queries on a planar graph stored in external memory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operatio...
详细信息
We present results related to satisfying shortest path queries on a planar graph stored in external memory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operations required to sort an array of length N: (1) We describe a blocking for rooted trees to support bottom-up traversals of these trees in O(K/B) I/Os, where K is the length of the traversed path. The space required to store the tree is O(N/B) blocks, where N is the number of vertices of the tree and B is the block size. (2) We give an algorithm for computing a (2)/(3)-separator of size O(rootN) for a given embedded planar graph. Our algorithm takes O(sort(N)) I/Os, provided that a breadth-first spanning tree is given. (3) We give an algorithm for triangulating embedded planar graphs in O(sort(N)) I/Os. We use these results to construct a data structure for answering shortest path queries on planar graphs. The data structure uses O(N-3/2/B) blocks of external memory and allows for a shortest path query to be answered in O((rootN + K)/DB) I/Os, where K is the number of vertices on the reported path and D is the number of parallel disks. (C) 2002 Elsevier Science B.V. All rights reserved.
As an alternative to the Fibonacci heap, we design a new data structure called a 2-3 heap, which supports n insert, n delete-min, and m decrease-key operations in O(m + n log n) time. Our experiments show the 2-3 heap...
详细信息
As an alternative to the Fibonacci heap, we design a new data structure called a 2-3 heap, which supports n insert, n delete-min, and m decrease-key operations in O(m + n log n) time. Our experiments show the 2-3 heap is more efficient. The new data structure will have a wide application in graph algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.
Given a graph G and target values r(u,v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u,v) int...
详细信息
Given a graph G and target values r(u,v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u,v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if for some constant k greater than or equal to 2 G is (k-1)-vertex-connected and r(u,v) is an element of {0,k} holds for u,v is an element of V. We then give a linear time algorithm which delivers a 3/2-approximation solution to the problem with a connected graph G and r(u,v) is an element of {0,2}, u,v is an element of V. (C) 2003 Elsevier B.V. All rights reserved.
This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time wi...
详细信息
This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n) rootlog n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m + n) log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n(2)) operations on the EREW PRAM. (C) 2002 Published by Elsevier Science B.V.
This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time wi...
详细信息
This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n) rootlog n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m + n) log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n(2)) operations on the EREW PRAM. (C) 2002 Published by Elsevier Science B.V.
The chromatic index problem-finding the minimum number of colours required for colouring the edges of a graph-is still unsolved for indifference graphs, whose vertices can be linearly ordered so that the vertices cont...
详细信息
The chromatic index problem-finding the minimum number of colours required for colouring the edges of a graph-is still unsolved for indifference graphs, whose vertices can be linearly ordered so that the vertices contained in the same maximal clique are consecutive in this order. We present new positive evidence for the conjecture: every non neighbourhood-overfull indifference graph can be edge coloured with maximum degree colours. Two adjacent vertices are twins if they belong to the same maximal cliques. A graph is reduced if it contains no pair of twin vertices. A graph is overfull if the total number of edges is greater than the product of the maximum degree by [n/2], where n is the number of vertices. We give a structural characterization for neighbourhood-overfull indifference graphs proving that a reduced indifference graph cannot be neighbourhood-overfull. We show that the chromatic index for all reduced indifference graphs is the maximum degree. We present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours. (C) 2002 Elsevier Science B.V. All rights reserved.
Using the specific structure of the minimal separators of AT-free graphs, we give a polynomial time algorithm that computes a triangulation whose width is no more than twice the treewidth of the input graph. (C) 2003 ...
详细信息
Using the specific structure of the minimal separators of AT-free graphs, we give a polynomial time algorithm that computes a triangulation whose width is no more than twice the treewidth of the input graph. (C) 2003 Elsevier B.V. All rights reserved.
We present results related to satisfying shortest path queries on a planar graph stored in external memory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operatio...
详细信息
ISBN:
(纸本)3540662006
We present results related to satisfying shortest path queries on a planar graph stored in external memory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operations required to sort an array of length N: (1) We describe a blocking for rooted trees to support bottom-up traversals of these trees in O(K/B) I/Os, where K is the length of the traversed path. The space required to store the tree is O(N/B) blocks, where N is the number of vertices of the tree and B is the block size. (2) We give an algorithm for computing a (2)/(3)-separator of size O(rootN) for a given embedded planar graph. Our algorithm takes O(sort(N)) I/Os, provided that a breadth-first spanning tree is given. (3) We give an algorithm for triangulating embedded planar graphs in O(sort(N)) I/Os. We use these results to construct a data structure for answering shortest path queries on planar graphs. The data structure uses O(N-3/2/B) blocks of external memory and allows for a shortest path query to be answered in O((rootN + K)/DB) I/Os, where K is the number of vertices on the reported path and D is the number of parallel disks. (C) 2002 Elsevier Science B.V. All rights reserved.
A graph is (P-5,gem)-free, when it does not contain P-5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P-4) as an ...
详细信息
ISBN:
(纸本)3540405437
A graph is (P-5,gem)-free, when it does not contain P-5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P-4) as an induced subgraph. Using a characterization of (P-5,gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [6], we obtain linear time algorithms for the following NP-complete problems on (P-5,gem)-free graphs: Minimum Coloring, Maximum Weight Stable Set, Maximum Weight Clique, and Minimum Clique Cover.
Let G(V, E) be an undirected weighted graph with \V\ = n, and \E\ = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, Es) such that the distance between any pair of vertices in the spanner is at most t times the...
详细信息
ISBN:
(纸本)3540404937
Let G(V, E) be an undirected weighted graph with \V\ = n, and \E\ = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, Es) such that the distance between any pair of vertices in the spanner is at most t times the distance between the two in the given graph. A 1963 girth conjecture of Erdos implies that Omega(n(1+1/k)) edges axe required in the worst case for any (2k - 1)-spanner, which has been proved for k = 1, 2, 3, 5. There exist polynomial time algorithms that can construct spanners with the size that matches this conjectured lower bound, and the best known algorithm takes O(mn(1/k)) expected running time. In this paper, we present an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound. Our algorithm requires local information for computing a spanner, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms.
暂无评论