204990201
On a problem of Hendry
A graph G is homogeneously traceable if for every vertex v there is a Hamiltonian path beginning at that vertex. Clearly every Hamiltonian graph is homogeneously traceable. Given a homogeneously traceable graph G, we can construct a new graph H(G) with the same vertex set V(G), called the Hamiltonian path graph of G in [l], in which two vertices are adjacent if and only if they are connected by a Hamiltonian path in G. Hendry [2] asked whether there are any homogeneously traceable graphs for which IE(G)I > IE(H(G))I. The following two theorems partially answer this question.
21169395
Small Circuit Double Covers of Cubic Multigraphs
Let G be a two-connected graph. A family F of circuits of G is called a circuit double cover (CDC) if each edge of G is contained in exactly two circuits of F. In this paper, we show that if a simple cubic graph G (G ? K4) of order n has a CDC, then G has a CDC containing at most n/2 circuits. This result establishes the equivalence of the circuit double cover conjecture (due to Szekeres, Seymour) and the small circuit double cover conjecture (due to Bondy) for any cubic graph. Actually, a stronger result is obtained in this paper for all loopless cubic graphs. Another result in this paper establishes an upper bound on the size of any CDC of a cubic graph.
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
8637971
Infinite paths in planar graphs II, structures and ladder nets
A graph is k-indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k − 1 infinite components. In 1971, NashWilliams conjectured that a 4-connected infinite planar graph contains a spanning 2-way infinite path if, and only if, it is 3-indivisible. In this paper, we prove a structural result for 2-indivisible infinite planar graphs. This structural result is then used to prove Nash-Williams conjecture for all 4-connected 2-indivisible infinite planar graphs. ∗Partially supported by NSF grants DMS-9531824 and DMS-9970527
1160338
Graph Connectivity After Path
Removal
Let G be a graph and
u, v be two distinct vertices of
G. A u—v path P is called nonseparating if
G—V(P) is connected. The purpose of this
paper is to study the number of nonseparating
u—v path for two arbitrary
vertices u and
v of a given graph. For a
positive integer k, we will
show that there is a minimum integer α(k) so that if G is an α(k)-connected graph and
u and v are two arbitrary vertices in
G, then there exist
k vertex disjoint paths
P1[u,v], P2[u,v], . . ., Pk[u,v], such that G—V (Pi[u,v]) is connected for every
i (i = 1, 2, ..., k). In fact, we will prove that
α(k) ≤ 22k+2. It is known that α(1) = 3.. A
result of Tutte showed that α(2) = 3. We show that α(3) = 6. In
addition, we prove that if G
is a 5-connected graph, then for every pair of vertices
u and v there exists a path
P[u, v] such that G—V(P[u,
v]) is 2-connected.
11130888
On 3-connected graphs with contractible edge covers of size k
Abstract We consider 3-connected graphs whose contractible edges can be covered by k vertices and show that they can be divided into finitely many infinite classes of graphs.
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.
10594579
Hard Queries can be Addressed with Query Splitting Plus Stepping Stones and Pathways
A key finding of the Reliable Information Access Workshop of 2003 was that in collections like those used for TREC 6-8, there are a number of hard queries for which no current search engine can return a high quality set of results. Our Stepping Stones and Pathways (SSP) approach may yield an effective solution to such hard problems, as well as support exploration of collections of content not well known to a person (with broad interest and/or complex information needs). Our initial and promising testing of SSP had users prepare two separate short queries in order to launch processing. However, since beginning with a single information need is a more typical initial situation, we have extended the SSP research by exploring query splitting, especially as might apply to handling hard queries. This paper summarizes our recent results and identifies some of the future work needed.
7132341
HASE: A Hybrid Approach to Selectivity Estimation for Conjunctive Predicates
Current methods for selectivity estimation fall into two broad categories, synopsis-based and sampling-based. Synopsis-based methods, such as histograms, incur minimal overhead at query optimization time and thus are widely used in commercial database systems. Sampling-based methods are more suited for ad-hoc queries, but often involve high I/O cost because of random access to the underlying data. Though both methods serve the same purpose of selectivity estimation, their interaction in the case of selectivity estimation for conjuncts of predicates on multiple attributes is largely unexplored. Our work aims at taking the best of both worlds, by making consistent use of synopses and sample information when they are both present. To achieve this goal, we propose HASE, a novel estimation scheme based on a powerful mechanism called generalized raking. We formalize selectivity estimation in the presence of single attribute synopses and sample information as a constrained optimization problem. By solving this problem, we obtain a new set of weights associated with the sampled tuples, which has the nice property of reproducing the known selectivities when applied to individual predicates. We discuss different variants of the optimization problem and provide algorithms for solving it. We also provide asymptotic error bounds on the estimate. Extensive experiments are performed on both synthetic and real data, and the results show that HASE significantly outperforms both synopsis-based and sampling-based methods.
8993397
A Novel Hybrid Crypto-Biometric Authentication Scheme for ATM Based Banking Applications
This paper studies the smartcard based fingerprint encrytion/auth-entication scheme for ATM banking systems. In this scheme, the system authenticates each user by both his/her possession (smartcard) and biometrics (fingerprint). A smartcard is used for the first layer of authentication. Based on the successful pass of the first layer authentication, a subsequent process of the biometric fingerprint authentication proceeds. The proposed scheme is fast and secure. Computer simulations and statistical analyze are presented.
1195630
DATIS: A Data Transfer Interface for SPMD Programs of Scientific Computing