Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be con...
详细信息
ISBN:
(纸本)3540281010
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be connected by two vertex-disjoint paths of length <= D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. These algorithms can be implemented in O(vertical bar V vertical bar log vertical bar V vertical bar a) time. (c) 2008 Elsevier B.V. All rights reserved.
We describe an O(n(3)/logn)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fred...
详细信息
We describe an O(n(3)/logn)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49-60, 1976), Takaoka (Inform. Process. Lett. 43:195-199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49-60, 1990), Han (Inform. Process. Lett. 91:245-250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278-289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921-932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones.
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be re...
详细信息
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue making effective use of the rapidly growing stores of variation data now being gathered. In this paper, we present two integer linear programming (ILP) formulations for finding the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven to be extremely efficient in practice on data sets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics that cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP. We further present a Web server that was developed based on the exponential-sized ILP that performs fast maximum parsimony inferences and serves as a front end to a database of precomputed phylogenies spanning the human genome.
We provide self-stabilizing algorithms to obtain and maintain a maximal matching, maximal independent set or minimal dominating set in a given system graph. They converge in linear rounds under a distributed or synchr...
详细信息
We provide self-stabilizing algorithms to obtain and maintain a maximal matching, maximal independent set or minimal dominating set in a given system graph. They converge in linear rounds under a distributed or synchronous daemon. They can be implemented in an ad hoc network by piggy-backing on the beacon messages that nodes already use.
For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the ...
详细信息
For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (For the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) One downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. In this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. In some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time. Most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or O(1)-wise independent sampler. The prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is not derived from the well-known Karger-Klein-Tarjan algorithm. In many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. Further, using our algorithm as a guide, we present a unified view of the existing "nongreedy" minimum spanning tree algorithms. Concepts from the Karger-Klein-Tarjan algorithm, such as F-lightness, MST verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic MST algorithms of Chazelle and Pettie-Ramachandran.
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be re...
详细信息
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue making effective use of the rapidly growing stores of variation data now being gathered. In this paper, we present two integer linear programming (ILP) formulations for finding the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven to be extremely efficient in practice on data sets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics that cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP. We further present a Web server that was developed based on the exponential-sized ILP that performs fast maximum parsimony inferences and serves as a front end to a database of precomputed phylogenies spanning the human genome.
The notion of "strength of connectedness" between pixels has been successfully used in image segmentation. We present extensions to these works, which can considerably improve the efficiency of object deline...
详细信息
The notion of "strength of connectedness" between pixels has been successfully used in image segmentation. We present extensions to these works, which can considerably improve the efficiency of object delineation tasks. A set of pixels is said to be a kappa-connected component with respect to a seed pixel, when the strength of connectedness of any pixel in that set with respect to the seed is higher than or equal to a threshold. We discuss two approaches that define objects based on kappa-connected components with respect to a given seed set: with and without competition among seeds. While the previous approaches either assume no competition with a single threshold for all seeds or eliminate the threshold for seed competition, we show that seeds with different thresholds can improve segmentation in both paradigms. We also propose automatic and user-friendly interactive methods to determining the thresholds. The proposed methods are presented in the framework of the image foresting transform, which naturally leads to efficient and correct graph algorithms. The improvements are demonstrated through several segmentation experiments involving medical images. Copyright (C) 2008 Paulo A. V. Miranda et al.
Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P an...
详细信息
ISBN:
(纸本)9781605604657
Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least εdn edges of G to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. In this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a constant number of queries. As a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. None of these properties was previously known to be testable even with o(n) queries. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.
A path cover of a graph G = (V, E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find...
详细信息
A path cover of a graph G = (V, E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in 0(1 V 19) time, to solve the path cover problem on distance-hereditary graphs. (C) 2007 Elsevier B.V. All rights reserved.
A new heuristic algorithm, PROBE_BA, which is based on the recently introduced metaheuristic paradigm Population-Reinforced Optimization-Based Exploration (PROBE), is proposed for solving the graph Partitioning Proble...
详细信息
A new heuristic algorithm, PROBE_BA, which is based on the recently introduced metaheuristic paradigm Population-Reinforced Optimization-Based Exploration (PROBE), is proposed for solving the graph Partitioning Problem. The "exploration" part of PROBE_BA is implemented by using the Differential-Greedy algorithm of Battiti and Bertossi and a modification of the Kernighan-Lin algorithm at the heart of Bui and Moon's Genetic Algorithm BFS_GBA. Experiments are used to investigate properties of PROBE and show that PROBE_BA compares favorably with other solution methods based on Genetic algorithms, Randomized Reactive Tabu Search, or more specialized multilevel partitioning techniques. In addition, PROBE_BA finds new best cut values for 10 of the 34 instances in Walshaw's graph Partitioning Archive.
暂无评论