27692910
Dominating cycles in regular 3-connected graphs
Abstract Let G be a 3-connected, k -regular graph on at most 4 k vertices. We show that, for k ⩾63, every longest cycle of G is a dominating cycle. We conjecture that G is in fact hamiltonian.
20128924
Long path connectivity of regular graphs
Abstract Any pair of vertices in a 4-connected non-bipartite k -regular graph are joined by a Hamilton path or a path of length at least 3 k −6.
1667264
Path extendability of claw-free graphs
Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S@?{x,y}=@A, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(
1145290
Hamilton cycles in regular 3-connected graphs
Abstract We show in this paper that for k ⩾63, every 3-connected, k -regular simple graph on at most 22 7 k vertices is hamiltonian.
4362564
More powerful closure operations on graphs
Abstract Bondy and Chvatal have observed the following result: G =( V , E ) is a simple graph of order n . If uv ∉ E and d ( u )+ d ( v )⩾ n , then G is Hamiltonian iff G + uv is Hamiltonian. Thus, we can obtain a graph C n ( G ), named the n -closure of G , from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n . Therefore, G is Hamiltonian if C n ( G ) is Hamiltonian. Moreover, Bondy and Chvatal [2] generalized this idea to several properties on G . In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chvatal.
41212780
Real-time rendering of 3D medical data sets
Interactive exploration of three dimension (3D) medical data sets is required by many applications, but the huge amount of computational time and storage space needed for rendering do not allow the visualization of large medical data sets by now. In this paper we present a new algorithm for rendering large medical data sets at interactive frame rates on standard PC hardware. The input data is converted into a compressed hierarchical wavelet representation in a preprocessing step. During rendering, the wavelet representation is decompressed on-the-fly and rendered using hardware texture mapping. The level of detail used for rendering is adapted to the local frequency spectrum of the data and its position relative to the viewer. Using a prototype implementation of the algorithm we were able to perform an interactive walkthrough of large medical data sets on a single of-the-shelf PC.
35564489
Accelerated 2D Image Processing on GPUs
Graphics processing units (GPUs) in recent years have evolved to become powerful, programmable vector processing units. Furthermore, the maximum processing power of current generation GPUs is roughly four times that of current generation CPUs (central processing units), and that power is doubling approximately every nine months, about twice the rate of Moore's law. This research examines the GPU's advantage at performing convolutionbased image processing tasks compared to the CPU. Straight-forward 2D convolutions show up to a 130:1 speedup on the GPU over the CPU, with an average speedup in our tests of 59:1. Over convolutions performed with the highly optimized FFTW routines on the CPU, the GPU showed an average speedup of 18:1 for filter kernel sizes from 3x3 to 29x29.
2274256
Overlay Networks with Linear Capacity Constraints
Overlay networks are virtual networks residing over the IP network; consequently, overlay links may share hidden lower level bottlenecks. Previous work has assumed an independent overlay model: a graph with independent link capacities. We introduce a model of overlays that incorporates correlated link capacities and linear capacity constraints (LCC) to formulate hidden shared bottlenecks; we refer to these as LCC-overlays. We define metrics to qualitatively measure overlay quality in terms of its accuracy (in representing the true network topology) and efficiency (that is, performance). Through analysis and simulations, we show that LCC-overlay is perfectly accurate and, hence, enjoys much higher efficiency than the inaccurate independent overlay. We discover that even a highly restricted LCC class-node-based LCC-yields near-optimal accuracy and significantly higher efficiency. We study two network flow problems in the context of LCC-graphs: widest path and maximum flow. We prove that Widest Path with LCC is NP-complete. We formulate Maximum Flow with LCC as a linear program and propose an efficient distributed algorithm to solve it. Based on the LCC model, we further study the problem of optimizing delay while still maintaining optimal or near-optimal bandwidth. We also outline a distributed algorithm to efficiently construct an overlay with node-based LCC.
14174120
Overlay Multicast with Inferred Link Capacity Correlations
We model the overlay using linear capacity constraints, which accurately and succinctly capture overlay link correlations. We show that finding a maximum-bandwidth multicast tree in an overlay with LCC is NP-complete and propose an efficient distributed heuristics algorithm.
27779170
Study of Dempster-Shafer theory for image segmentation applications
Abstract This paper addresses a new knowledge model using the Dempster–Shafer's theory of evidence for image segmentation and fusion. The salient aspects of the proposed method are at two levels. Firstly, mass distributions in Dempster–Shafer theory are directly derived from image histograms. Secondly, the fusion process does not start from one single frame of discernment, as it was done in most of the previously reported works, but does start from first defining two independent frames of discernment associated with the two images to be fused, and then combining them for forming a new frame of discernment. The strategy used to define mass distributions in the combined framework is discussed in detail. The proposed fusion method is illustrated in the context of image segmentation. The obtained results show the robustness of the method.