An asteroidal triple (AT) is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an AT. We show that ...
详细信息
An asteroidal triple (AT) is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an AT. We show that there is an O(n(4)) time algorithm to compute the maximum weight of an independent set for AT-free graphs. Furthermore, we obtain O(n(4)) time algorithms to solve the independent dominating set and the independent perfect dominating set problems on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally, we observe that the problems clique and partition into cliques remain NP-complete when restricted to AT-free graphs.
An ear decomposition for a graph G is a sequence of paths (P-1, P-2,..., P-k) such that if, for each i, G(i) = G - P-1 -...- P-i, then P-i is a maximal path of degree-two vertices in G(i-1) whose endpoint(s) in G(i) h...
详细信息
An ear decomposition for a graph G is a sequence of paths (P-1, P-2,..., P-k) such that if, for each i, G(i) = G - P-1 -...- P-i, then P-i is a maximal path of degree-two vertices in G(i-1) whose endpoint(s) in G(i) have degree at least two, and G(k) is a union of disjoint cycles. Ear decomposition has become a standard tool in the design of graph algorithms, especially parallel connectivity algorithms. We show that the existence of two natural variations on ear decomposition can be tested in polynomial time. The first is a weak long-ear decomposition, in which every ear (path) is either disconnecting or is at least as long as a given bound B. The second is a strong short-ear decomposition, in which every ear is non-disconnecting and has length at most B. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewi...
详细信息
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition. (C) 1999 Academic Press.
We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an ef...
详细信息
We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an NP-hardness proof and thus establish computational intractability.
The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools...
详细信息
The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness. in a variety of contexts on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of "authoritative" information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of "hub pages" that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph;these connections in turn motivate additional heuristics for link-based analysis.
We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is determinist...
详细信息
We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log(2) n) time with O(Delta(2)(n + m)/ log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem. (C) 1999-Elsevier Science B.V. All rights reserved
This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval gra...
详细信息
This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(n log log n) or O(n + m) time, where m is the number of edges in the corresponding interval graphs. (C) 1999 John Wiley & Sons, Inc. Networks 34: 1-10, 1999.
In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with...
详细信息
In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).
We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown top...
详细信息
We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+n log n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.
Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC 1 . This is done by showing that 3-colouring a linked list is NC 1 -reducible to minimally colouring an interval graph. H...
详细信息
Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC 1 . This is done by showing that 3-colouring a linked list is NC 1 -reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC 1 . For the CRCW PRAM model, an o( log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o( log n) chromatic number and a known interval representation. In particular, when the chromatic number is O(( log n) 1-ε ), 0<ε<1, the algorithm runs in O( log n/ log log n) time. Also, an O( log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω( log n/ log log n) time, on a CRCW PRAM, with a polynomial number of processors.
暂无评论