16450923
The circumference of a graph with no K3, t-minor
It was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least |G|^l^o^g^"^3^2, where |G| denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function @b(t)>0 for t>=3, such that every 3-connected graph G with no K"3","t-minor, t>=3, contains a cycle of length at least |G|^@b^(^t^). We prove that this conjecture is true with @b(t)=log"8"t"^"t"^"+"^"12. We also show that every 2-connected graph with no K"2","t-minor, t>=3, contains a cycle of length at least |G|/t^t^-^1.
122697425
Infinite paths in planar graphs I: Graphs with radial nets
Let G be an infinite 4-connected planar graph such that the deletion of any finite set of vertices from G results in exactly one infinite component. Dean et al. proved that either G admits a radial net or a special subgraph of G admits a ladder net, and they used these nets to show that G contains a spanning 1-way infinite path. In this paper, we show that if G admits a radial net, then G also contains a spanning 2-way infinite path. This is a step towards a conjecture of Nash-Williams. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 147–162, 2004
18288842
Finding Four Independent Trees
Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an $O(|V|^2)$ algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an $O(|V|^3)$ algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.
8099466
Nonseparating Planar Chains in 4-Connected Graphs
In this paper, we describe an O(|V(G)||E(G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs.
13571183
Chain Decompositions of 4-Connected Graphs
In this paper we give a decomposition of a $4$-connected graph $G$ into nonseparating chains, which is similar to an ear decomposition of a $2$-connected graph. We also give an $O(|V(G)|^2|E(G)|)$ algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to $O(|V(G)|^3)$. This decomposition will be used to find four independent spanning trees in a $4$-connected graph.
29305561
Positively curved cubic plane graphs are finite
Let G be an infinite plane graph such that G is locally finite and every face of G is bounded by a cycle. Then G is said to be positively curved if, for every vertex x of G, 1− d(x)/2 + Σx∈F 1 |F | > 0, where the summation is taken over all facial cycles F containing x. Note that if G is positively curved then the maximum degree of G is at most 5. As a discrete analogue of a result in Riemannian geometry, Higuchi conjectured that if G is positively curved then G is finite. In this paper, we establish this conjecture for cubic graphs. Partially supported by a grant from China Scholarship Council Partially supported by NSF grant DMS-9970527
13475547
Towards estimating the number of distinct value combinations for a set of attributes
Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.
26301648
Data Integrity Framework and Language Support for Active Web Intermediaries
With the maturity of content adaptation technologies (such as I-CAP and OPES) in web intermediaries and of content personalization in the network, data integrity has already become a key concern when such technologies are deployed. To address this issue, we propose a data integrity framework with the following functionalities: (i) a server can specify its authorizations, (ii) active web intermediaries can provide value-added services in accordance with the server’s intentions, and more importantly, (iii) a client is facilitated to verify the received message with the server’s authorizations and intermediaries’ footprints. With the actual implementation of our data integrity framework in web (content and proxy) servers and clients, we show the feasibility and practicability of our proposed design through its low performance overhead and possible data (re)use.
1195630
DATIS: A Data Transfer Interface for SPMD Programs of Scientific Computing
2653351
Fingerprint images encryption via multi-scroll chaotic attractors
This paper proposes a chaotic fingerprint images encryption approach. An image of a fingerprint is encrypted via a two-dimensional (2D) chaotic sequence obtained from multi-scroll chaotic attractors. Initial values of the chaotic attractors are served as the private key, which can be generated from the pixel distribution of the binary images of the captured fingerprints. Due to the dynamic uncertainties in the acquisition process of fingerprint images, the keys generated from the pixel value distribution are virtually random. With the elaborately designed 2D chaotic sequence, the encrypted fingerprint images have balanced 0-1 ratio and ideal nonlinearity. Only with the valid private key can the images of fingerprint be recovered. Simulation results and 2D-DFT validate this chaotic encryption approach.
1886676
Monitoring k-nearest neighbor queries over moving objects
Many location-based applications require constant monitoring of k-nearest neighbor (k-NN) queries over moving objects within a geographic area. Existing approaches to this problem have focused on predictive queries, and relied on the assumption that the trajectories of the objects are fully predictable at query processing time. We relax this assumption, and propose two efficient and scalable algorithms using grid indices. One is based on indexing objects, and the other on queries. For each approach, a cost model is developed, and a detailed analysis along with the respective applicability is presented. The object-indexing approach is further extended to multi-levels to handle skewed data. We show by experiments that our grid-based algorithms significantly outperform R-tree-based solutions. Extensive experiments are also carried out to study the properties and evaluate the performance of the proposed approaches under a variety of settings.