bluuebunny/crossref_metadata_2025 huggingface dataset:
Centrifuge modelling of the pushover failure of an electricity transmission tower
Authors: Richards D. J. , White D. J. , Lehane B. M.
Published: April 2010

Centrifuge model tests were conducted to examine foundation failure mechanisms during rapid horizontal pushover of an electricity transmission line support tower, simulating a broken transmission line response or wind gust loading. A model transmission tower supported on four pad foundations in clay and backfilled with sand was loaded horizontally and the loads at each foundation were measured during fast and slow pushover. The tests examined the influence of tensile resistance mobilized at the underside of the footings, which is difficult to reliably incorporate within design practice due to a lack of accepted quantitative design methods. The measured performance of the tower footings was compared with results from a series of tests where a single footing is subjected to purely vertical loading in compression and tension and was found to be in good agreement. The tower response was back-analysed as a simple push–pull model and the calculated uplift capacity of the footing backfill provided a close match to the observed response of the tower footings subjected to slow pushover. During fast pushover, the additional capacity mobilized due to tensile resistance (suction) created by the reverse bearing capacity beneath the base of the footings subjected to uplift was quantified using a suction capacity factor.
Hydraulic conductivity and consolidation response of mixtures of mine waste rock and tailings
Authors: Wickland Benjamin E. , Wilson G. Ward , Wijewickreme Dharma
Published: April 2010

Hydraulic conductivity and consolidation behaviour are examined for an alternative mine waste disposal technique. One type of waste rock, one type of tailings, and mixtures of the same waste rock and tailings were tested in bench-scale and column studies. Specimens 150 mm in diameter were tested for hydraulic conductivity by falling-head method alternated with one-dimensional consolidation, specimens 300 mm in diameter were tested for one-dimensional consolidation response, and specimens 1 m in diameter were tested for self-weight consolidation behaviour in 6 m high columns. Deformation of mixtures under one-dimensional loading was similar to that of waste rock alone and much less than that of tailings alone. Hydraulic conductivity of mixtures was similar to that of tailings alone and independent of specimen diameter. Mixture behaviour was attributed to a homogeneous structure including waste rock in particle-to-particle contact and a continuous, saturated matrix of tailings. The results indicate that mixing waste rock and tailings can produce dense deposits with values of hydraulic conductivity that are orders of magnitude lower than those of waste rock alone, thereby limiting fluxes through the waste and the associated potential for acid rock drainage. Mixture deposits will also have less consolidation-related settlement than tailings, thus improving stability and aiding reclamation.
Three-dimensional ground displacements from static pipe bursting in stiff clay
Authors: Brachman R. W.I. , McLeod H. A. , Moore I. D. , Take W. A.
Published: April 2010

Three-dimensional ground surface displacements from 20 m long static pipe-bursting experiments are reported. These experiments were conducted with firm-to-stiff clay backfill in a trench with very stiff clay sidewalls at three different burial depths. Multiple digital cameras and image analysis were used to quantify the surface response as the expander progressed through the original pipe. The experiments quantified the upward surface movement as the expander approached, the effect of burial depth on maximum uplift, and the final amount of uplift after it decreased to a residual displacement. The experiments also quantified the axially forward ground surface movement as the expander approached, reaching maximum just ahead of the expander, and decreasing to almost zero after the expander had passed by. Lateral movements of the ground surface away from the centreline are also reported, which were essentially zero at the centre line, increasing to a maximum and then decreasing with distance from the centreline. The three different burial depths produced in effect the same width of vertical surface response with the displacements contained within 1.5 m on either side of the centreline, suggesting that the very stiff clay trench walls had a dominant influence on the measured displacements.
CONSISTENT THERMODYNAMICS FOR QUASIPARTICLE BOSON SYSTEM WITH ZERO CHEMICAL POTENTIAL
Authors: YIN SHAOYU , SU RU-KENG
Published: April 2010

The thermodynamic consistency of quasiparticle boson system with effective mass m* and zero chemical potential is studied. We take the quasiparticle gluon plasma model as a toy model. The failure of previous treatments based on traditional partial derivative is addressed. We show that a consistent thermodynamic treatment can be applied to such boson system provided that a new degree of freedom m* is introduced in the partial derivative calculation. A pressure modification term different from the vacuum contribution is derived based on the new independent variable m*. A complete and self-consistent thermodynamic treatment for quasiparticle system, which can be widely applied to effective mass models, has been constructed.
A DUAL FOUR-DIMENSIONAL SUPERSTRING
Authors: DEO B. B. , JENA P. K.
Published: April 2010

The 26-dimensional bosonic string, first suggested by Nambu and Goto, is reduced to a four-dimensional superstring by using two species of six and five Majorana fermions as proposed by Deo. These two species of fermions differ in their "neutrino-like" phase, and are vectors in the bosonic representation SO (d-1, 1). Using Polchinski's equivalence between operators and states, we can write the Virasoro generators for four-dimensional string theory. The theory is shown to give the same results as given by other superstrings and also reveals the well-known aspects of four-dimensional string theory. The bosons and the fermions are found to be the basis for constructing this string theory which includes gravity and exhibits strong–weak coupling duality as well as the usual electric–magnetic duality. This formalism is used to calculate the metric tensor as well as the entropy–area relation for a black hole.
TRADER SPECIES WITH DIFFERENT DECISION STRATEGIES AND PRICE DYNAMICS IN FINANCIAL MARKETS: AN AGENT-BASED MODELING PERSPECTIVE
Authors: ZHANG WEI , LI GEN , XIONG XIONG , ZHANG YONG JIE
Published: April 2010

Investors with different trading strategies can be viewed as different "species" in financial markets. Since the asset price is ultimately determined by the individual trading decisions, the combination and evolution of different trader species in financial market ecology will have great impact to the price dynamics. Considering the limitations and shortcomings of traditional analytical approaches in financial economics in dealing with this issue, an agent-based computational model is introduced in this paper. With the co-existence of 3-type trader species that make different decisions based on their own beliefs and constrains, it is found that although rational speculation destabilizes the price process with the presence of positive feedback strategy, as suggested in the literature, introducing extra noise trading behavior to the market will make the price process back to a more stationary situation, meaning that the market will be healthier if more diversified trader species co-exist in the markets.
B-SPLINE ANALYTICAL REPRESENTATION OF THE MEAN ENVELOPE FOR EMPIRICAL MODE DECOMPOSITION
Authors: ZHENG TIANXIANG , YANG LIHUA
Published: April 2010

This paper investigates how the mean envelope, the subtrahend in the sifting procedure for the Empirical Mode Decomposition (EMD) algorithm, represents as an expansion in terms of basis. To this end, a novel approach that gives an alternative analytical expression using B-spline functions is presented. The basic concept lies mainly on the idea that B-spline functions form a basis for the space of splines and have refined-node representations by knot insertion. This newly-developed expression is essentially equivalent to the conventional one, but gives a more explicit formulation on this issue. For the purpose of establishing the mathematical foundation of the EMD methodology, this study may afford a favorable opportunity in this direction.
FUSION OF SURVEILLANCE IMAGES IN INFRARED AND VISIBLE BAND USING CURVELET, WAVELET AND WAVELET PACKET TRANSFORM
Authors: SHAH PARUL , MERCHANT S. N. , DESAI U. B.
Published: April 2010

This paper presents two methods for fusion of infrared (IR) and visible surveillance images. The first method combines Curvelet Transform (CT) with Discrete Wavelet Transform (DWT). As wavelets do not represent long edges well while curvelets are challenged with small features, our objective is to combine both to achieve better performance. The second approach uses Discrete Wavelet Packet Transform (DWPT), which provides multiresolution in high frequency band as well and hence helps in handling edges better. The performance of the proposed methods have been extensively tested for a number of multimodal surveillance images and compared with various existing transform domain fusion methods. Experimental results show that evaluation based on entropy, gradient, contrast etc., the criteria normally used, are not enough, as in some cases, these criteria are not consistent with the visual quality. It also demonstrates that the Petrovic and Xydeas image fusion metric is a more appropriate criterion for fusion of IR and visible images, as in all the tested fused images, visual quality agrees with the Petrovic and Xydeas metric evaluation. The analysis shows that there is significant increase in the quality of fused image, both visually and quantitatively. The major achievement of the proposed fusion methods is its reduced artifacts, one of the most desired feature for fusion used in surveillance applications.
FRAMES OF SUBSPACES FOR BANACH SPACES
Authors: JAIN P. K. , KAUSHIK S. K. , KUMAR VARINDER
Published: April 2010

Frames of subspaces for Banach spaces have been introduced and studied. Examples and counter-examples to distinguish various types of frames of subspaces have been given. It has been proved that if a Banach space has a Banach frame, then it also has a frame of subspaces. Also, a necessary and sufficient condition for a sequence of projections, associated with a frame of subspaces, to be unique has been given. Finally, we consider complete frame of subspaces and prove that every weakly compactly generated Banach space has a complete frame of subspaces.
COMBINATORIAL PROOFS OF CERTAIN IDENTITIES INVOLVING PARTIAL THETA FUNCTIONS
Authors: KIM BYUNGCHAN
Published: April 2010

In this brief note, we give combinatorial proofs of two identities involving partial theta functions. As an application, we prove an identity for the product of partial theta functions, first established by Andrews and Warnaar. We also provide a generalization of the first two identities and give a combinatorial proof of the generalized identities.
The datapath merging problem in reconfigurable systems
Authors: Souza Cid C. de , Lima Andre M. , Araujo Guido , Moreano Nahri B.
Published: April 2010

In this paper, we investigate the data path merging problem (DPM) in reconfigurable systems. DPM is modeled as a graph optimization problem and is shown to be
NP
-hard. An Integer Programming (IP) formulation of the problem is presented and some valid inequalities for the convex hull of integer solutions are introduced. These inequalities form the basis of a branch-and-cut algorithm that we implemented. This algorithm was used to compute lower bounds for a set of DPM instances, allowing us to assess the performance of two heuristics proposed earlier in the literature for the problem. Moreover, the branch-and-cut algorithm also was proved to be a valuable tool to solve small-sized DPM instances to optimality.
Increased bit-parallelism for approximate and multiple string matching
Authors: Hyyrö Heikki , Fredriksson Kimmo , Navarro Gonzalo
Published: April 2010

Bit-parallelism permits executing several operations simultaneously over a set of bits or numbers stored in a single computer word. This technique permits searching for the approximate occurrences of a pattern of length
m
in a text of length
n
in time
O
(⌈
m
/
w
⌉
n
), where
w
is the number of bits in the computer word. Although this is asymptotically the optimal bit-parallel speedup over the basic
O
(
mn
) time algorithm, it wastes bit-parallelism's power in the common case where
m
is much smaller than
w
, since
w
−
m
bits in the computer words are unused. In this paper, we explore different ways to increase the bit-parallelism when the search pattern is short. First, we show how multiple patterns can be packed into a single computer word so as to search for all them simultaneously. Instead of spending
O
(
rn
) time to search for
r
patterns of length
m
≤
w
/2, we need
O
(⌈
rm
/
w
⌉
n
) time. Second, we show how the mechanism permits boosting the search for a single pattern of length
m
≤
w
/2, which can be searched for in
O
(⌈
n
/⌊
w
/
m
⌋⌉) bit-parallel steps instead of
O
(
n
). Third, we show how to extend these algorithms so that the time bounds essentially depend on
k
instead of
m
, where
k
is the maximum number of differences permitted. Finally, we show how the ideas can be applied to other problems such as multiple exact string matching and one-against-all computation of edit distance and longest common subsequences. Our experimental results show that the new algorithms work well in practice, obtaining significant speedups over the best existing alternatives, especially on short patterns and moderate number of differences allowed. This work fills an important gap in the field, where little work has focused on very short patterns.
A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem
Authors: Santos Haroldo G. , Ochi Luiz S. , Souza Marcone J.F.
Published: April 2010

The Class/Teacher Timetabling Problem (CTTP) deals with the weekly scheduling of encounters between teachers and classes of an educational institution. Since CTTP is a NP-hard problem for nearly all of its variants, the use of heuristic methods for its resolution is justified. This paper presents an efficient Tabu Search (TS) heuristic with two different memory based diversification strategies for CTTP. Results obtained through an application of the method to a set of real world problems show that it produces better solutions than a previously proposed TS found in the literature and faster times are observed in the production of good quality solutions.
A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
Authors: Bracht Evandro C. , Meira Luis A. A. , Miyazawa F. K.
Published: April 2010

We consider the uniform metric labeling problem. This NP-hard problem considers how to assign objects to labels respecting assignment and separation costs. The known approximation algorithms are based on solutions of large linear programs and are impractical for moderate- and large-size instances. We present an 8logn-approximation algorithm that can be applied to large-size instances. The algorithm is greedy and is analyzed by a primal-dual technique. We implemented the presented algorithm and two known approximation algorithms and compared them at randomized instances. The gain of time was considerable with small error ratios. We also show that the analysis is tight, up to a constant factor.
Cache-Friendly implementations of transitive closure
Authors: Penner Michael , Prasanna Viktor K.
Published: April 2010

The topic of cache performance has been well studied in recent years. Compiler optimizations exist and optimizations have been done for many problems. Much of this work has focused on dense linear algebra problems. At first glance, the Floyd--Warshall algorithm appears to fall into this category. In this paper, we begin by applying two standard cache-friendly optimizations to the Floyd--Warshall algorithm and show limited performance improvements. We then discuss the unidirectional space time representation (USTR). We show analytically that the USTR can be used to reduce the amount of processor-memory traffic by a factor of O(√C), where C is the cache size, for a large class of algorithms. Since the USTR leads to a tiled implementation, we develop a tile size selection heuristic to intelligently narrow the search space for the tile size that minimizes total execution time. Using the USTR, we develop a cache-friendly implementation of the Floyd--Warshall algorithm. We show experimentally that this implementation minimizes the level-1 and level-2 cache misses and TLB misses and, therefore, exhibits the best overall performance. Using this implementation, we show a 2x improvement in performance over the best compiler optimized implementation on three different architectures. Finally, we show analytically that our implementation of the Floyd--Warshall algorithm is asymptotically optimal with respect to processor-memory traffic. We show experimental results for the Pentium III, Alpha, and MIPS R12000 machines using problem sizes between 1024 and 2048 vertices. We demonstrate improved cache performance using the Simplescalar simulator.
Algorithms for dynamic multicast key distribution
Authors: Goshi Justin , Ladner Richard E.
Published: April 2010

We study the problem of multicast key distribution for group security. Secure group communication systems typically rely on a group key, which is a secret shared among the members of the group. This key is used to provide privacy by encrypting all group communications. Because groups can be large and highly dynamic, it becomes necessary to change the group key in a scalable and secure fashion when members join and leave the group. We present a series of algorithms for solving this problem based on key trees. The algorithms attempt to minimize the worst-case communication cost of updates by maintaining balanced key tree structures. We focus on the trade-off between the communication cost because of the structure of the tree and that due to the overhead of restructuring the tree to maintain its balanced structure. The algorithms are analyzed for worst-case tree structure bounds and evaluated empirically via simulations.
A dynamic topological sort algorithm for directed acyclic graphs
Authors: Pearce David J. , Kelly Paul H. J.
Published: April 2010

We consider the problem of maintaining the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has inferior time complexity compared with the best previously known result, we find that its simplicity leads to better performance in practice. In addition, we provide an empirical comparison against the three main alternatives over a large number of random DAGs. The results show our algorithm is the best for sparse digraphs and only a constant factor slower than the best on dense digraphs.
Experiments on exact crossing minimization using column generation
Authors: Chimani Markus , Gutwenger Carsten , Mutzel Petra
Published: April 2010

The crossing number of a graph
G
is the smallest number of edge crossings in any drawing of
G
into the plane. Recently, the first branch-and-cut approach for solving the crossing number problem has been presented in Buchheim et al. [2005]. Its major drawback was the huge number of variables out of which only very few were actually used in the optimal solution. This restricted the algorithm to rather small graphs with low crossing number.

In this article, we discuss two column generation schemes; the first is based on traditional algebraic pricing, and the second uses combinatorial arguments to decide whether and which variables need to be added. The main focus of this article is the experimental comparison between the original approach and these two schemes. In addition, we evaluate the quality achieved by the best-known crossing number heuristic by comparing the new results with the results of the heuristic.
Speeding up spatial approximation search in metric spaces
Authors: Figueroa Karina , Chavez Edgar , Navarro Gonzalo , Paredes Rodrigo
Published: April 2010

Proximity searching consists of retrieving from a database those elements that are similar to a query object. The usual model for proximity searching is a metric space where the distance, which models the proximity, is expensive to compute. An index uses precomputed distances to speedup query processing. Among all the known indices, the baseline for performance for about 20 years has been AESA. This index uses an iterative procedure, where at each iteration it first chooses the next promising element (“pivot”) to compare to the query, and then it discards database elements that can be proved not relevant to the query using the pivot. The next pivot in AESA is chosen as the one minimizing the sum of lower bounds to the distance to the query proved by previous pivots. In this article, we introduce the new index
iAESA
, which establishes a new performance baseline for metric space searching. The difference with AESA is the method to select the next pivot. In iAESA, each candidate sorts previous pivots by closeness to it, and chooses the next pivot as the candidate whose order is most similar to that of the query. We also propose a modification to AESA-like algorithms to turn them into probabilistic algorithms.

Our empirical results confirm a consistent improvement in query performance. For example, we perform as few as 60% of the distance evaluations of AESA in a database of documents, a very important and difficult real-life instance of the problem. For the probabilistic algorithm, we perform in a database of faces up to 40% of the comparisons made by the best alternative algorithm to retrieve the same percentage of the correct answer. Based on the empirical results, we conjecture that the new probabilistic AESA-like algorithms will become, as AESA had been for exact algorithms, a reference point establishing, in practice, a lower bound on how good a probabilistic proximity search algorithm can be.
Algorithms for longer OLED lifetime
Authors: Eisenbrand Friedrich , Karrenbauer Andreas , Xu Chihao
Published: April 2010

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize the amplitude of the electrical current flowing through the diodes, which has a direct impact on the lifetime of such a display. The optimization problem consist of finding a decomposition of an image into subframes with special structural properties that allow the display driver to lower the stress on the diodes. For monochrome images, we present an algorithm that finds an optimal solution of this problem in linear time. Moreover, we consider an online version of the problem in which we have to take a decision for one row based on a constant number of rows in the lookahead. In this framework, this algorithm has a tight competitive ratio. A generalization of this algorithm computes near-optimal solutions of real-world instances in real time.
The overture initiative integrating tools for VDM
Authors: Larsen Peter Gorm , Battle Nick , Ferreira Miguel , Fitzgerald John , Lausdahl Kenneth , Verhoef Marcel
Published: April 2010

Overture is a community-based initiative that aims to develop a common open-source platform integrating a range of tools for constructing and analysing formal models of systems using VDM. The mission is to both provide an industrial-strength tool set for VDM and also to provide an environment that allows researchers and other stakeholders to experiment with modifications and extensions to the tools and language. This paper presents the current status and future vision of the Overture project.
Layer-free upward crossing minimization
Authors: Chimani Markus , Gutwenger Carsten , Mutzel Petra , Wong Hoi-Ming
Published: April 2010

An upward drawing of a DAG
G
is a drawing of
G
in which all arcs are drawn as curves increasing monotonically in the vertical direction. In this article, we present a new approach for upward crossing minimization, that is, finding an upward drawing of a DAG
G
with as few crossings as possible. Our algorithm is based on a two-stage upward planarization approach, which computes a feasible upward planar subgraph in the first step and reinserts the remaining arcs by computing constraint-feasible upward insertion paths. An experimental study shows that the new algorithm leads to much better results than existing algorithms for upward crossing minimization, including the classical Sugiyama approach.
Engineering burstsort
Authors: Sinha Ranjan , Wirth Anthony
Published: April 2010

Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. This approach has earlier been demonstrated to be efficient on modern cache-based processors [Sinha & Zobel, JEA 2004]. In this article, we introduce improvements that reduce by a significant margin the memory requirement of Burstsort: It is now less than 1% greater than an in-place algorithm. These techniques can be applied to existing variants of Burstsort, as well as other string algorithms such as for string management.

We redesigned the buckets, introducing sub-buckets and an index structure for them, which resulted in an order-of-magnitude space reduction. We also show the practicality of moving some fields from the trie nodes to the insertion point (for the next string pointer) in the bucket; this technique reduces memory usage of the trie nodes by one-third. Importantly, the trade-off for the reduction in memory use is only a very slight increase in the running time of Burstsort on real-world string collections. In addition, during the bucket-sorting phase, the string suffixes are copied to a small buffer to improve their spatial locality, lowering the running time of Burstsort by up to 30%. These memory usage enhancements have enabled the copy-based approach [Sinha et al., JEA 2006] to also reduce the memory usage with negligible impact on speed.
Interrupt handler migration and direct interrupt scheduling for rapid scheduling of interrupt-driven tasks
Authors: Lee Jupyung , Park Kyu Ho
Published: April 2010

In this article, we propose two techniques that aim to minimize the scheduling latency of high-priority interrupt-driven tasks, named the Interrupt Handler Migration (IHM) and Direct Interrupt Scheduling (DIS). The IHM allows the interrupt handler to be migrated from the interrupt handler thread to the corresponding target process so that additional context switch can be avoided and the cache hit ratio with respect to the data generated by the interrupt handler can be improved. In addition, the DIS allows the shortest path reserved for urgent interrupt-process pairs to be laid between the interrupt arrival and target process by dividing a series of interrupt-driven operations into nondeferrable and deferrable operations. Both the IHM and DIS can be combined in a natural way and can operate concurrently. These techniques can be applied to all kinds of interrupt handlers with no modification to them. The proposed techniques not only reduce the scheduling latency, but also resolve the interrupt-driven priority inversion problem.

We implemented a prototype in the Linux 2.6.19 kernel after adding real-time patches. Experimental results show that the scheduling latency is significantly reduced by up to 84.2% when both techniques are applied together. When the Linux OS runs on an ARM-based embedded CPU running at 200MHz, the scheduling latency can become as low as 30
μ
s, which is much closer to the hardware-specific limitations. By lowering the scheduling latency, the limited CPU cycles can be consumed more for user-level processes and less for system-level tasks, such as interrupt handling and scheduling.
Potential for personalization
Authors: Teevan Jaime , Dumais Susan T. , Horvitz Eric
Published: April 2010

Current Web search tools do a good job of retrieving documents that satisfy the most common intentions associated with a query, but do not do a very good job of discerning different individuals' unique search goals. We explore the variation in what different people consider relevant to the same query by mining three data sources: (1)
explicit
relevance judgments, (2) clicks on search results (a
behavior-based implicit
measure of relevance), and (3) the similarity of desktop content to search results (a
content-based implicit
measure of relevance). We find that people's explicit judgments for the same queries differ greatly. As a result, there is a large gap between how well search engines could perform if they were to tailor results to the individual, and how well they currently perform by returning results designed to satisfy everyone. We call this gap the
potential for personalization
. The two implicit indicators we studied provide complementary value for approximating this variation in result relevance among people. We discuss several uses of our findings, including a personalized search system that takes advantage of the implicit measures by ranking personally relevant results more highly and improving click-through rates.
Approximating fractional hypertree width
Authors: Marx Dániel
Published: April 2010

Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work, Constraint Satisfaction Problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this article, we show that for every fixed
w
≥ 1, there is a polynomial-time algorithm that, given a hypergraph
H
with fractional hypertree width at most
w
, computes a fractional hypertree decomposition of width
O
(
w
3
) for
H
. This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if
H
is a class of hypergraphs with bounded fractional hypertree width, then a CSP restricted to instances whose structure is in
H
is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean conjunctive queries, and conjunctive query containment polynomial-time solvable.
Maximal biconnected subgraphs of random planar graphs
Authors: Panagiotou Konstantinos , Steger Angelika
Published: April 2010

Let
C
be a class of labeled connected graphs, and let C

n

be a graph drawn uniformly at random from graphs in
C
that contain exactly
n
vertices. Denote by
b
(ℓ; C

n

) the number of blocks (i.e., maximal biconnected subgraphs) of C

n

that contain exactly ℓ vertices, and let
lb
(C

n

) be the number of vertices in a largest block of C

n

. We show that under certain general assumptions on
C
, C

n

belongs with high probability to one of the following categories:

(1)
lb
(C

n

) ∼
cn
, for some explicitly given
c
=
c
(
C
), and the second largest block is of order
n
α
, where 1 > α = α(
C
), or

(2)
lb
(C

n

) =
O
(log
n
), that is, all blocks contain at most logarithmically many vertices.

Moreover, in both cases we show that the quantity
b
(ℓ; C

n

) is concentrated for all ℓ and we determine its expected value. As a corollary we obtain that the class of planar graphs belongs to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Authors: Madani Omid , Thorup Mikkel , Zwick Uri
Published: April 2010

We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of
O
(
mn
), improving the recent bound of
O
(
mn
2
) obtained by Andersson and Vorbyov [2006]. We also present a randomized
O
(
m
1/2
n
2
)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an
O
(
mn
2
)-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].
Periodicity testing with sublinear samples and space
Authors: Ergun Funda , Muthukrishnan S. , Sahinalp Cenk
Published: April 2010

In this work, we are interested in periodic trends in long data streams in the presence of computational constraints. To this end; we present algorithms for discovering periodic trends in the combinatorial property testing model in a data stream
S
of length
n
using
o
(
n
) samples and space.

In accordance with the property testing model, we first explore the notion of being “close” to periodic by defining three different notions of self-distance through relaxing different notions of exact periodicity. An input
S
is then called approximately periodic if it exhibits a small self-distance (with respect to any one self-distance defined). We show that even though the different definitions of exact periodicity are equivalent, the resulting definitions of self-distance and approximate periodicity are not; we also show that these self-distances are constant approximations of each other. Afterwards, we present algorithms which distinguish between the two cases where
S
is exactly periodic and
S
is far from periodic with only a constant probability of error.

Our algorithms sample only
O
(√
n
log
2
n
) (or
O
(√
n
log
4
n
), depending on the self-distance) positions and use as much space. They can also find, using
o
(
n
) samples and space, the largest/smallest period, and/or all of the approximate periods of
S
. These algorithms can also be viewed as working on streaming inputs where each data item is seen once and in order, storing only a sublinear (
O
(√
n
log
2
n
) or
O
(√
n
log
4
n
)) size sample from which periodicities are identified.
Central angiotensin I increases fetal AVP neuron activity and pressor responses
Authors: Shi Lijun , Mao Caiping , Zeng Fanxing , Hou Jianquan , Zhang Hong , Xu Zhice
Published: April 2010

Angiotensin (Ang) II plays a critical role in cardiovascular homeostasis and neuroendocrine regulation. Little is known about whether central angiotensin-converting enzyme (ACE) is functional in the fetal brain. We investigated cardiovascular and neuroendocrinological responses to intracerebroventricular (icv) application of Ang I in the chronically prepared near-term ovine fetus in utero and examined the action sites marked by c-fos expression in the fetal hypothalamus. ACE mRNA was detected in the specific central areas. Intracerebroventricular Ang I significantly increased fetal blood pressure and c-fos expression in the supraoptic nuclei (SON) and the paraventricular nuclei (PVN) in the hypothalamus, accompanied by an increase of fetal plasma arginine vasopressin (AVP). Double labeling demonstrated that AVP neurons in the fetal SON and PVN were expressing c-fos. Captopril, an inhibitor of ACE, significantly suppressed fetal pressor responses and plasma AVP. Double labeling experiments showed colocalization of AT1 receptor (AT1R) and c-fos expression in both SON and PVN following icv Ang I. The results indicate that central endogenous ACE has been functional at least at the last third of gestation and the endogenous brain renin-angiotensin system-mediated pressor responses and AVP release via AT1Rs by acting at the sites consistent with the cardiovascular network in the hypothalamus.
Properties of GABAergic Neurons in the Rostral Solitary Tract Nucleus in Mice
Authors: Wang Min , Bradley Robert M.
Published: April 2010

The rostral nucleus of the solitary tract (rNST) plays a pivotal role in taste processing. The rNST contains projection neurons and interneurons that differ in morphology and intrinsic membrane properties. Although characteristics of the projection neurons have been detailed, similar information is lacking on the interneurons. We determined the intrinsic properties of the rNST GABAergic interneurons using a transgenic mouse model that expresses enhanced green fluorescent protein under the control of a GAD67 promoter. Glutamic acid decarboxylase–green fluorescent protein (GAD67–GFP) neurons were distributed throughout the rNST but were concentrated in the ventral subdivision with minimal interaction with the terminal field of the afferent input. Furthermore, the density of the GAD67–GFP neurons decreased in more rostral areas of rNST. In whole cell recordings, GAD67–GFP neurons responded with either an initial burst (73%), tonic (18%), or irregular (9%) discharge pattern of action potentials (APs) in response to membrane depolarization. These three groups also differed in passive and AP characteristics. Initial burst neurons had small ovoid or fusiform cell bodies, whereas tonic firing neurons had large multipolar or fusiform cell bodies. Irregular firing neurons had larger spherical soma. Some of the initial burst and tonic firing neurons were also spontaneously active. The GAD67–GFP neurons could also be categorized in subgroups based on colocalization with somatostatin and parvalbumin immunolabeling. Initial burst neurons would transmit the early dynamic portion of the encoded sensory stimuli, whereas tonic firing neurons could respond to both dynamic and static components of the sensory input, suggesting different roles for GAD67–GFP neurons in taste processing.
Compensatory proteome adjustments imply tissue-specific structural and metabolic reorganization following episodic hypoxia or anoxia in the epaulette shark (Hemiscyllium ocellatum)
Authors: Dowd W. Wesley , Renshaw Gillian M. C. , Cech Joseph J. , Kültz Dietmar
Published: April 2010

The epaulette shark ( Hemiscyllium ocellatum ) represents an ancestral vertebrate model of episodic hypoxia and anoxia tolerance at tropical temperatures. We used two-dimensional gel electrophoresis and mass spectrometry-based proteomics approaches, combined with a suite of physiological measures, to characterize this species' responses to 1) one episode of anoxia plus normoxic recovery, 2) one episode of severe hypoxia plus recovery, or 3) two episodes of severe hypoxia plus recovery. We examined these responses in the cerebellum and rectal gland, two tissues with high ATP requirements. Sharks maintained plasma ionic homeostasis following all treatments, and activities of Na+/K+-ATPase and caspase 3/7 in both tissues were unchanged. Oxygen lack and reoxygenation elicited subtle adjustments in the proteome. Hypoxia led to more extensive proteome responses than anoxia in both tissues. The cerebellum and rectal gland exhibited treatment-specific responses to oxygen limitation consistent with one or more of several strategies: 1) neurotransmitter and receptor downregulation in cerebellum to prevent excitotoxicity, 2) cytoskeletal/membrane reorganization, 3) metabolic reorganization and more efficient intracellular energy shuttling that are more consistent with sustained ATP turnover than with long-term metabolic depression, 4) detoxification of metabolic byproducts and oxidative stress in light of continued metabolic activity, particularly following hypoxia in rectal gland, and 5) activation of prosurvival signaling. We hypothesize that neuronal morphological changes facilitate prolonged protection from excitotoxicity via dendritic spine remodeling in cerebellum (i.e., synaptic structural plasticity). These results recapitulate several highly conserved themes in the anoxia and hypoxia tolerance, preconditioning, and oxidative stress literature in a single system. In addition, several of the identified pathways and proteins suggest potentially novel mechanisms for enhancing anoxia or hypoxia tolerance in vertebrates. Overall, our data show that episodic hypoxic or anoxic exposure and recovery in the epaulette shark amplifies a constitutive suite of compensatory mechanisms that further prepares them for subsequent insults.
Controlling the Eccentricity of Polar Lunar Orbits with Low‐Thrust Propulsion
Authors: Winter O. C. , Mourão D. C. , Melo C. F. de , Macau E. N. , Ferreira J. L. , Carvalho J. P. S.
Published: April 2010

It is well known that lunar satellites in polar orbits suffer a high increase on the eccentricity due to the gravitational perturbation of the Earth. The final fate of such satellites is the collision with the Moon. Therefore, the control of the orbital eccentricity leads to the control of the satellite′s lifetime. In the present work we study this problem and introduce an approach in order to keep the orbital eccentricity of the satellite at low values. The whole work was made considering two systems: the 3‐body problem, Moon‐Earth‐satellite, and the 4‐body problem, Moon‐Earth‐Sun‐satellite. First, we simulated the systems considering a satellite with initial eccentricity equals to 0.0001 and a range of initial altitudes between 100 km and 5000 km. In such simulations we followed the evolution of the satellite′s eccentricity. We also obtained an empirical expression for the length of time needed to occur the collision with the Moon as a function of the initial altitude. The results found for the 3‐body model were not significantly different from those found for the 4‐body model. Secondly, using low‐thrust propulsion, we introduced a correction of the eccentricity every time it reached the value 0.05.
S100A1: A Regulator of Striated Muscle Sarcoplasmic Reticulum Ca2+Handling, Sarcomeric, and Mitochondrial Function
Authors: Völkers Mirko , Rohde David , Goodman Chelain , Most Patrick
Published: March 2010

Calcium (Ca2+) signaling plays a key role in a wide range of physiological functions including control of cardiac and skeletal muscle performance. To assure a precise coordination of both temporally and spatially transduction of intracellularCa2+oscillations to downstream signaling networks and target operations,Ca2+cycling regulation in muscle tissue is conducted by a plethora of diverse molecules.Ca2+S100A1 is a member of theCa2+-binding S100 protein family and represents the most abundant S100 isoform in cardiac and skeletal muscle. Early studies revealed distinct expression patterns of S100A1 in healthy and diseased cardiac tissue from animal models and humans. Further elaborate investigations uncovered S100A1 protein as a basic requirement for striated muscleCa2+handling integrity. S100A1 is a critical regulator of cardiomyocyteCa2+cycling and contractile performance. S100A1-mediated inotropy unfolds independent and on top ofβAR-stimulated contractility with unchangedβAR downstream signaling. S100A1 has further been detected at different sites within the cardiac sarcomere indicating potential roles in myofilament function. More recently, a study reported a mitochondrial location of S100A1 in cardiomyocytes. Additionally, normalizing the level of S100A1 protein by means of viral cardiac gene transfer in animal heart failure models resulted in a disrupted progression towards cardiac failure and enhanced survival. This brief review is confined to the physiological and pathophysiological relevance of S100A1 in cardiac and skeletal muscleCa2+handling with a particular focus on its potential as a molecular target for future therapeutic interventions.
B3LYP Study on Reduction Mechanisms from O2 to H2O at the Catalytic Sites of Fully Reduced and Mixed‐Valence Bovine Cytochrome c Oxidases
Authors: Yoshioka Yasunori , Mitani Masaki
Published: April 2010

Reduction mechanisms of oxygen molecule to water molecules in the fully reduced (FR) and mixed‐valence (MV) bovine cytochrome c oxidases (CcO) have been systematically examined based on the B3LYP calculations. The catalytic cycle using four electrons and four protons has been also shown consistently. The MV CcO catalyses reduction to produce one water molecule, while the FR CcO catalyses to produce two water molecules. One water molecule is added into vacant space between His240 and His290 in the catalytic site. This water molecule constructs the network of hydrogen bonds of Tyr244, farnesyl ethyl, and Thr316 that is a terminal residue of the K‐pathway. It plays crucial roles for the proton transfer to the dioxygen to produce the water molecules in both MV and FR CcOs. Tyr244 functions as a relay of the proton transfer from the K‐pathway to the added water molecule, not as donors of a proton and an electron to the dioxygen. The reduction mechanisms of MV and FR CcOs are strictly distinguished. In the FR CcO, the Cu atom at the CuB site maintains the reduced state Cu(I) during the process of formation of first water molecule and plays an electron storage. At the final stage of formation of first water molecule, the Cu(I) atom releases an electron to Fe‐O. During the process of formation of second water molecule, the Cu atom maintains the oxidized state Cu(II). In contrast with experimental proposals, the K‐pathway functions for formation of first water molecule, while the D‐pathway functions for second water molecule. The intermediates, PM, PR, F, and O, obtained in this work are compared with those proposed experimentally.
Parametric Set-Valued Vector Quasi-Equilibrium Problems
Authors: Fan Liya , Li Aiqin
Published: April 2010

Two kinds of parametric set-valued vector quasi-equilibrium problems are introduced. The existence of solutions to these problems is studied. The upper and lower semicontinuities of their solution maps with respect to the parameters are investigated.
Intensity-Modulated Radiotherapy for a Rendu-Osler-Weber Disease Patient with Recurrent Severe Epistaxis: A Case Report
Authors: Niyazi Maximilian , Caversaccio Marco-Domenico , Dubach Patrick , Geretschläger Andreas , Arnold Andreas , Belka Claus , Aebersold Daniel M. , Blumstein Norbert M.
Published: March 2010

We present a case of a Rendu-Osler-Weber disease patient with recurrent life threatening epistaxis demanding multiple blood transfusions despite of repetitive endoscopic laser and electrocoagulations, endovascular embolisation, septodermoplasty, and long-term intranasal dressings. As alternative treatment modalities repeatedly failed and the patient became almost permanently dependent on nasal dressing, we performed a highly conformal intensity-modulated radiotherapy of the nasal cavity; a total dose of 50 Gy in 2 Gy single fractions was applied. The therapy was very well tolerated, no acute toxicities occurred. Two weeks after the last radiation dose had been applied, the nasal dressing could be removed without problems. Endoscopical control revealed an almost avascular white mucosa without any trace of bleeding spots; previously existing hemangiomas and crusts had disappeared. After a 1-year-follow up, the patient had no significant recurrent epistaxis.
Dynamics of Entanglement between a Quantum Dot Spin Qubit and a Photon Qubit inside a Semiconductor High‐Q Nanocavity
Authors: Seigneur Hubert Pascal , Gonzalez Gabriel , Leuenberger Michael Niklaus , Schoenfeld Winston Vaughan
Published: March 2010

We investigate in this paper the dynamics of entanglement between a QD spin qubit and a single photon qubit inside a quantum network node, as well as its robustness against various decoherence processes. First, the entanglement dynamics is considered without decoherence. In the small detuning regime (Δ = 78 μeV), there are three different conditions for maximum entanglement, which occur after 71, 93, and 116 picoseconds of interaction time. In the large detuning regime (Δ = 1.5 meV), there is only one peak for maximum entanglement occurring at 625 picoseconds. Second, the entanglement dynamics is considered with decoherence by including the effects of spin‐nucleus and hole‐nucleus hyperfine interactions. In the small detuning regime, a decent amount of entanglement (35% entanglement) can only be obtained within 200 picoseconds of interaction. Afterward, all entanglement is lost. In the large detuning regime, a smaller amount of entanglement is realized, namely, 25%. And, it lasts only within the first 300 picoseconds.