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.
16363205
Approximating Longest Cycles in Graphs with Bounded Degrees
Jackson and Wormald conjecture that if $G$ is a 3-connected $n$-vertex graph with maximum degree $d\ge 4$, then $G$ has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.
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.
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
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.
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.
2329429
Embodied data objects: tangible interfaces to information appliances
This paper describes the idea of embodied data objects. Using this concept, everyday objects can be used to represent bits and bytes of active information. These data objects can be used to interact with information-appliance-like devices that provide specific services as dictated by the context of interaction. The inherent affordances of physical artifacts are leveraged to make the interaction with these service-oriented devices intuitive and natural. We describe the idea of embodied data objects, followed by the design and implementation of two such service-oriented devices: a presentation projector and a printer.
16035202
An efficient transistor optimizer for custom circuits
We present an equation-based transistor size optimizer that minimizes delay of custom circuits. Our method uses static timing analysis to find the critical paths and numerical methods to optimize transistor sizes continuously without using simulation. Consequently, it is faster than simulation-based optimizers, and more general than standard cell optimizers. We demonstrate its efficacy and accuracy on a complete dynamic adder presented, where we achieve a 54% speed-up, and final critical path delay that match Spice within 1%.
1493351
Circuit Design Style for Energy Efficiency: LSDL and Compound Domino
Introduction of sub-90nm technology has made a profound impact on circuit designs. Thus, it requires understanding of existing design styles for desired energy-efficiency. We compare adder designs in the energy-delay space, implemented with Limited Switch Dynamic Logic (LSDL) and Compound Domino Logic (CD) in a 65nm SOI technology. Evaluation results show that LSDL can provide more than 35% energy savings than CD with 25% switching activity at relaxed cycle times greater than 10.5 F04.
12758700
Distributed cache updating for the dynamic source routing protocol
On-demand routing protocols use route caches to make routing decisions. Due to mobility, cached routes easily become stale. To address the cache staleness issue, prior work in DSR used heuristics with ad hoc parameters to predict the lifetime of a link or a route. However, heuristics cannot accurately estimate timeouts because topology changes are unpredictable. In this paper, we propose proactively disseminating the broken link information to the nodes that have that link in their caches. We define a new cache structure called a cache table and present a distributed cache update algorithm. Each node maintains in its cache table the information necessary for cache updates. When a link failure is detected, the algorithm notifies all reachable nodes that have cached the link in a distributed manner. The algorithm does not use any ad hoc parameters, thus making route caches fully adaptive to topology changes. We show that the algorithm outperforms DSR with path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches. We conclude that proactive cache updating is key to the adaptation of on-demand routing protocols to mobility.
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.