In this paper, we address the problem of automatically assembling shredded documents. We propose a two-step algorithmic framework. First, we digitize each fragment of a given document and extract shape- and content-ba...
详细信息
In this paper, we address the problem of automatically assembling shredded documents. We propose a two-step algorithmic framework. First, we digitize each fragment of a given document and extract shape- and content-based local features. Based on these multimodal features, we identify pairs of corresponding points on all pairs of fragments using an SVM classifier. Each pair is considered a point of attachment for aligning the respective fragments. In order to restore the layout of the document, we create a document graph in which nodes represent fragments and edges correspond to alignments. We assign weights to the edges by evaluating the alignments using a set of inter-fragment constraints which take into account shape- and content-based information. Finally, we use an iterative algorithm that chooses the edge having the highest weight during each iteration. However, since selecting edges corresponds to combining groups of fragments and thus provides new evidence, we reevaluate the edge weights after each iteration. We quantitatively evaluate the effectiveness of our approach by conducting experiments on a novel dataset. It comprises a total of 120 pages taken from two magazines which have been shredded and annotated manually. We thus provide the means for a quantitative evaluation of assembly algorithms which, to the best of our knowledge, has not been done before.
An undirected graph G with diameter k is said to be goal-minimally k-diametric if for every edge uv of G the distance d(G-uv)(x, y) > k if and only if {x, y} = {u, v}. We describe an efficient algorithm for determi...
详细信息
An undirected graph G with diameter k is said to be goal-minimally k-diametric if for every edge uv of G the distance d(G-uv)(x, y) > k if and only if {x, y} = {u, v}. We describe an efficient algorithm for determining whether a given graph is goal-minimally k-diametric or not. In addition, we illustrate the use of the algorithm on a large graph with diameter 26. (C) 2013 Elsevier B.V. All rights reserved.
A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-sta...
详细信息
A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9];this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. (C) 2014 Elsevier B.V. All rights reserved.
Kou, Markowsy, and Berman (1981) described a procedure for finding a Steiner tree for a connected, undirected distance graph with a specified subset of the set of vertices. A new implementation of that 1981 algorithm...
详细信息
Kou, Markowsy, and Berman (1981) described a procedure for finding a Steiner tree for a connected, undirected distance graph with a specified subset of the set of vertices. A new implementation of that 1981 algorithm is described. Using the new implementation, it is possible to find a Steiner tree whose total distance of all edges is at most 2 times one minus (one divided by the minimum number of leaves greater than the total distance of all edges of a Steiner minimal tree). The solution is both faster and simpler than previous solutions to the problem since it reduces the question being considered to a shortest path and a minimum spanning tree calculation. The algorithm: 1. constructs the complete distance graph for the connected undirected distance graph (G), 2. finds a minimum spanning tree for the complete distance graph, 3. constructs a subgraph of G, 4. finds a minimum spanning tree of the subgraph of G, and 5. constructs a Steiner tree from the minimum spanning tree so no leaves in the Steiner tree are Steiner vertices.
作者：
Toda, SNihon Univ
Coll Humanities & Sci Dept Appl Math Tokyo 1568550 Japan
We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log(3)/(2) n), where n denotes the number of nodes...
详细信息
We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log(3)/(2) n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)(2) log(2) n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This: class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.
Let G = (V, E) be a connected graph such that each edge e is an element of E and each vertex nu is an element of V are weighted by nonnegative reals w(e) and h(nu), respectively. Let r be a vertex designated as a root...
详细信息
Let G = (V, E) be a connected graph such that each edge e is an element of E and each vertex nu is an element of V are weighted by nonnegative reals w(e) and h(nu), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p subtrees T-1, T-2,..., T-p such that each T-i contains X-i boolean OR {r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in T-i and the weights of vertices in X-i. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p cycles C-1, C-2,..., C-P such that C-i contains X-i boolean OR {r} so as to minimize the maximum cost of the cycles, where the cost of C-i is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p + 1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p + 1))-approximation algorithm to the MRCC with a metric (G, w).
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G ...
详细信息
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G or there are at least two k-list colorings. The existing research results indicate that K-1,K-1,K-1,K-r and K-1*r,K-3 have the property M(3), and in addition K-1*5,K-r and K-1*r,K-5 have the property M(4) for every r >= 2. The results above are extended to every k in this paper. We will show that for every r >= 1, k >= 2, K-1*r,K- (2k-3) and K-1*(2k-3),K-r have the property M(k). The conclusion will pave the way to characterizing unique k-list colorable complete multipartite graphs. (C) 2014 Elsevier B.V. All rights reserved.
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E wher...
详细信息
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E where !V! = n. In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.
Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) =...
详细信息
Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) = (sic) for any pair of adjacent vertices u and v. An n-[p]coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the triangular lattice (called hexagonal graphs) has important applications in cellular networks. In this article we provide an algorithm to find a 7-[3]coloring of triangle-free hexagonal graphs in linear time, without using the fourcolor theorem, which solves the open problem stated by Sau. Snarl and Zerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a 14-[6]coloring. (C) 2012 Elsevier B.V. All rights reserved.
Untargeted metabolomics makes it possible to identify compounds that undergo significant changes in concentration in different experimental conditions. The resulting metabolomic profile characterizes the perturbation ...
详细信息
Untargeted metabolomics makes it possible to identify compounds that undergo significant changes in concentration in different experimental conditions. The resulting metabolomic profile characterizes the perturbation concerned, but does not explain the underlying biochemical mechanisms. Bioinformatics methods make it possible to interpret results in light of the whole metabolism. This knowledge is modelled into a network, which can be mined using algorithms that originate in graph theory. These algorithms can extract sub-networks related to the compounds identified. Several attempts have been made to adapt them to obtain more biologically meaningful results. However, there is still no consensus on this kind of analysis of metabolic networks. This review presents the main graph approaches used to interpret metabolomic data using metabolic networks. Their advantages and drawbacks are discussed, and the impacts of their parameters are emphasized. We also provide some guidelines for relevant sub-network extraction and also suggest a range of applications for most methods.
暂无评论