This paper presents a new algorithm to determine 1-extendable graphs. Let G = (VE) be a graph with at least 4 vertices. If the graph G has a perfect matching and every edge of E(G) is contained in a perfect matching o...
详细信息
ISBN:
(纸本)9789889867140
This paper presents a new algorithm to determine 1-extendable graphs. Let G = (VE) be a graph with at least 4 vertices. If the graph G has a perfect matching and every edge of E(G) is contained in a perfect matching of G, then G is said to be Iextendable. Our algorithm runs in O(vertical bar V vertical bar vertical bar E vertical bar) time in the worst case and its complexity is the same as the algorithm developed by Carvalho and Cheriyan Ill. But the procedure of our algorithm is much simpler than the latter one. Furthermore, an implementation is given in details.
Given a weighted undirected graph G = (V, E), a tree ( respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree ( r...
详细信息
Given a weighted undirected graph G = (V, E), a tree ( respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree ( resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of G. Arkin, Halldorsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Konemann, Konjevod, Parekh, and Sinha ( 2003) study the linear programming relaxations and improve both factors to 3. We describe in the first part of the paper a 2-approximation algorithm for the metric case of tree cover. In the second part, we will consider a generalized version of tree (resp. tour) covers problem which is to find a minimum tree ( resp. tours) which covers a subset D subset of E of G. We show that the algorithms of Konemann et al. can be adapted for the generalized tree and tours covers problem with the same factors.
graph algorithms are becoming increasingly important for solving many problems in scientific computing, data mining and other domains. As these problems grow in scale, parallel computing resources are required to meet...
详细信息
graph algorithms are becoming increasingly important for solving many problems in scientific computing, data mining and other domains. As these problems grow in scale, parallel computing resources are required to meet their computational and memory requirements. Unfortunately, the algorithms, software, and hardware that have worked well for developing mainstream parallel scientific applications are not necessarily effective for large-scale graph problems. In this paper we present the inter-relationships between graph problems, software, and parallel hardware in the current state of the art and discuss how those issues present inherent challenges in solving large-scale graph problems. The range of these challenges suggests a research agenda for the development of scalable high-performance software for graph problems.
The National Cancer Institute has collected a large database of uterine cervix images, termed "cervigrams" for cervical cancer screening research. Tissues of interest within the cervigram, in particular the ...
详细信息
ISBN:
(纸本)9781424406715
The National Cancer Institute has collected a large database of uterine cervix images, termed "cervigrams" for cervical cancer screening research. Tissues of interest within the cervigram, in particular the lesions, are of varying sizes and complex, non-convex shapes. The current work proposes a new methodology that enables the segmentation of non-convex regions, thus providing a major step forward towards cervigram tissue detection and lesion delineation. The framework transitions from pixels to a set of small coherent regions (superpixels), which are grouped bottom-up into larger, non-convex, perceptually similar regions, utilizing a new graph-cut criterion and agglomerative clustering. Superpixels similarity is computed via a combined region and boundary information measure. Results for a set of 120 cervigrams, manually marked by a medical expert, are shown.
Real data are ``dirty.' Despite active research on integrity constraints enforcement and data cleaning, real data in real database applications are still dirty. To make matters worse, both diverse formats/usages o...
详细信息
Real data are ``dirty.' Despite active research on integrity constraints enforcement and data cleaning, real data in real database applications are still dirty. To make matters worse, both diverse formats/usages of modern data and demands for large-scale data handling make this problem even harder. In particular, to surmount the challenges for which conventional solutions against this problem no longer work, we focus on one type of problems known as the Entity Resolution (ER) -- the process of identifying and merging duplicate entities determined to represent the same real-world object. Despite the fact that the problem has been studied extensively, it is still not trivial to de-duplicate complex entities among a large number of *** this thesis, we have studied three specialized types of ER problems: (1) the Split Entity Resolution (SER) problem, in which instances of the same entity type mistakenly appear under different name variants; (2) the Mixed Entity Resolution (MER) problem, in which instances of different entities appear together for their homonymous names; and (3) the Grouped Entity Resolution (GER) problem, in which instances of entities do not carry any name or description by which ER techniques can be utilized, and thus the contents of entities are exploited as a group of elements. For each type of problems, we have developed a novel scalable solution. Especially, for the GER problem, we have developed two graph theoretic algorithms - one based on Quasi-Clique and the other based on Bipartite Matching, and experimentally validated the superiority of the proposed solutions.
Consider the problem of locating servers in a network for the purpose of storing data, performing an application, etc., so that at least one server will be available to clients even if up to k component failures occur...
详细信息
Consider the problem of locating servers in a network for the purpose of storing data, performing an application, etc., so that at least one server will be available to clients even if up to k component failures occur throughout the network. Letting G = (V, E) be the graph with vertex set V and edge set E representing the topology of the network, and letting L subset of V be a set of potential locations for the servers, a fundamental problem is to determine a minimum-size set S subset of L such that the network remains connected to S even if up to k component failures occur throughout the network. We say that such a set S is k-fault-tolerant. In this paper we present an algebraic characterization of k-fault-tolerant sets in terms of a. ne embeddings of G in k-dimensional Euclidean space. Employing this characterization, we present a polynomial-time Monte Carlo algorithm for computing a minimum-size k-fault-tolerant subset S of L. In fact, we solve the following more general problem for directed networks: given a digraph G = (V, E) (an undirected graph is equivalent to a symmetric digraph) and a subset L subset of V, we find a k-fault-tolerant subset S of L having minimum cost, where a unary integer cost c(v) is associated with locating a server at vertex v epsilon V.
We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(mn(2)) to O(m(2)) and the space c...
详细信息
We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(mn(2)) to O(m(2)) and the space complexity from O(n(3)) to O(m+n), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O(mn(2)) to O(n(3)) and the complexity of the independent set and clique cover problems is improved from O(n(4)) to O(mn). The space complexity of our optimization algorithms is O(m + n).
We propose a check-digit scheme that makes use of graph vertex coloring. It complements known schemes, which rather make use of the graph structure. Our scheme can be used simultaneously with them to compensate for mu...
详细信息
We propose a check-digit scheme that makes use of graph vertex coloring. It complements known schemes, which rather make use of the graph structure. Our scheme can be used simultaneously with them to compensate for mutual weaknesses. We show that feasibility of the proposed scheme increases with the size of the number whose digits are checked, and with the overall probability of digit errors.
We provide evidence that nonlinear dimensionality reduction, clustering, and data set parameterization can be solved within one and the same framework. The main idea is to define a system of coordinates with an explic...
详细信息
We provide evidence that nonlinear dimensionality reduction, clustering, and data set parameterization can be solved within one and the same framework. The main idea is to define a system of coordinates with an explicit metric that reflects the connectivity of a given data set and that is robust to noise. Our construction, which is based on a Markov random walk on the data, offers a general scheme of simultaneously reorganizing and subsampling graphs and arbitrarily shaped data sets in high dimensions using intrinsic geometry. We show that clustering in embedding spaces is equivalent to compressing operators. The objective of data partitioning and clustering is to coarse-grain the random walk on the data while at the same time preserving a diffusion operator for the intrinsic geometry or connectivity of the data set up to some accuracy. We show that the quantization distortion in diffusion space bounds the error of compression of the operator, thus giving a rigorous justification fork-means clustering in diffusion space and a precise measure of the performance of general clustering algorithms.
Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their correspon...
详细信息
Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n - 2) x (2n - 2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n - 1) x n. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论