To realize a non-contact, non-invasive and fast measurement of skin blood flow, we have developed the laser speckle contrast analysis (LASCA) technique. The LASCA method is a spatial domain method, based on the aggreg...
详细信息
ISBN:
(纸本)0819427829
To realize a non-contact, non-invasive and fast measurement of skin blood flow, we have developed the laser speckle contrast analysis (LASCA) technique. The LASCA method is a spatial domain method, based on the aggregate of pixels composing a captured laser speckle image. The contrast calculation operates directly on these pixels. In this paper, we present the computer algorithms to achieve a real-time solution for monitoring capillary blood how and velocity First, we present an improved naive LASCA algorithm with the running time O(k(2)n), where n is the total number of pixels and k x k represents the size of the subimage considered. Then, we describe a fast LASCA algorithm, which takes time O(icn) to calculate the local contrasts. Finally, We use the fast sequential algorithm to design the first LASCA parallel algorithm to run on the CREW PRAM with the running time O(k/p n), where p is the number of processors. Experimental result shows that, to process a laser speckle image with the size of 640 x 480, it takes only about one second using the fast LASCA algorithm. Furthermore, our parallel algorithm is easily implemented to run under the Windows NT environment by using multi-threads technique.
We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of are insertions in O(nm) worst case total time, where n is the number of nodes and m is the number of arcs af...
详细信息
We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of are insertions in O(nm) worst case total time, where n is the number of nodes and m is the number of arcs after the insertions. This compares favorably with the time required to recompute DFS from scratch by using Tarjan's Theta(n + m) algorithm any time a sequence of Omega(n) are insertions must be handled. In particular, over a sequence of Theta(m) arc insertions our algorithm requires O(n) amortized time per operation, and its worst case time is O(n + m). Our algorithm relies on an original characterization of a DFS-forest in terms of a relaxed planar embedding of the graph. Besides the basic representation of the graphs in term of adjacency lists, O(n) additional space is required. Although the problem of the dynamic maintenance of a DFS-tree was pointed out about one decade ago, this paper provides the first solution to this problem for nontrivial classes of graphs. (C) 1997 Elsevier Science B.V.
The algorithmic complexity of the graph clustering problem when restricted to special classes of graphs is investigated. We develop results showing the intractability of graph clustering and the hardness of approximat...
详细信息
The algorithmic complexity of the graph clustering problem when restricted to special classes of graphs is investigated. We develop results showing the intractability of graph clustering and the hardness of approximating minimum graph clusterings. Our main result is a polynomial time approximation algorithm of constant worst case ratio (at most 3) which computes ak-clustering for graphs having a dominating diametral path. (C) 1997 Published by Elsevier Science B.V.
Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates ...
详细信息
Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates a regression solution with median residual no more than twice the optimal median residual. Random sampling is used to provide a simple O(n log(2) n) expected time algorithm in the two-dimensional case that is successful with high probability. This algorithm is also extended to arbitrary dimension d with O(n(d-1) log n) worst-case complexity for fixed d > 2. (C) 1997 Elsevier Science B.V.
Using a linear time many-one reduction from the problem TOTAL DOMINATING SET to the problem DOMINATING SET we show how to obtain efficient algorithms to compute a minimum cardinality total dominating set on a variety ...
详细信息
Using a linear time many-one reduction from the problem TOTAL DOMINATING SET to the problem DOMINATING SET we show how to obtain efficient algorithms to compute a minimum cardinality total dominating set on a variety of graph classes, among them permutation graphs, dually chordal graphs and k-polygon graphs. (C) 1997 Elsevier Science B.V.
We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, lo...
详细信息
We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CCRW PRAM, f(n) is o(n(3)). On the randomized CRCW PRAM we are able to achieve time complexity O (n(3)/p + log n) using p processors.
We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes;earlier results focused on ed...
详细信息
We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes;earlier results focused on edge-set insertions and single edge deletions. We give a generic result which asserts maintainability after deleting any ''antichain'' of edges. Many maintainability results follow, including after deleting any edge from acyclic graphs, after deleting any subset of all incoming (outgoing) edges to (from) any antichain family of strongly connected components (SCC), and after deleting any antichain of nodes. We then shaw maintainability after deleting all edges (or nodes) in any antichain family of SCCs. Finally, we show that maintainability after node deletions is at least as hard as after edge deletions. (C) 1997 Elsevier Science B.V.
We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algo...
详细信息
We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algorithm is a parallelization of King's Linear time sequential algorithm for the problem. (C) 1997 Elsevier Science B.V.
In this paper, an algorithm for mapping positive polarity Reed-Muller (PPRM) coefficients from canonical sum of products (CSOP) coefficients is presented. Another algorithm for mapping CSOP coefficients is also presen...
详细信息
In this paper, an algorithm for mapping positive polarity Reed-Muller (PPRM) coefficients from canonical sum of products (CSOP) coefficients is presented. Another algorithm for mapping CSOP coefficients is also presented, Both algorithms are more space efficient than the existing algorithms. (C) 1997 Elsevier Science B.V.
Let G be a simple undirected graph and let w be an assignment of non-negative weights to the vertices of G. For a proper r-coloring c of the vertices of G, we denote by w(c)(i) the maximum weight of a vertex in color ...
详细信息
Let G be a simple undirected graph and let w be an assignment of non-negative weights to the vertices of G. For a proper r-coloring c of the vertices of G, we denote by w(c)(i) the maximum weight of a vertex in color class i, and denote by w(c) the sum, Sigma(i=1)(r) w(c)(i), of these maximum weights. Let sigma(G, w, r) be the minimum of w(c) among all r-colorings of G, and let sigma(G, w) be the minimum among sigma(G, w, r) for all r greater than or equal to 1. A coloring c of a weighted graph G is called optimal coloring if w(c) = sigma(G, w). We shall consider the problem that how many colors are needed in an optimal coloring of a weighted graph Gi We relate this number to the First-Fit coloring algorithm and show that for optimal colorings of trees, the number of colors needed could be arbitrarily large, and for graphs of path-width k, the number of colors needed in an optimal coloring is at most 40(k + 1). We then give a polynomial time algorithm to decide, for a fixed r, whether or not a weighted graph G of bounded tree-width satisfies sigma(G, w, r) less than or equal to q, for any given number q. (C) 1997 Elsevier Science B.V.
暂无评论