bluuebunny/crossref_metadata_2025 huggingface dataset:
Finding large stable matchings
Authors: Irving Robert W. , Manlove David F.
Published: April 2010

When ties and incomplete preference lists are permitted in the stable marriage and hospitals/residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size, and position of ties. In this article, we present two new heuristics for finding large stable matchings in variants of these problems in which ties are on one side only. We describe an empirical study involving these heuristics and the best existing approximation algorithm for this problem. Our results indicate that all three of these algorithms perform significantly better than naive tie-breaking algorithms when applied to real-world and randomly-generated data sets and that one of the new heuristics fares slightly better than the other algorithms, in most cases. This study, and these particular problem variants, are motivated by important applications in large-scale centralized matching schemes.
SHARC
Authors: Bauer Reinhard , Delling Daniel
Published: April 2010

During recent years, impressive speed-up techniques for Dijkstra's have been developed. Unfortunately, the most advanced techniques use bidirectional search, which makes it hard to use them in scenarios where a backward search is prohibited. Even worse, such scenarios are widely spread (e.g., timetable-information systems or time-dependent networks).

In this work, we present a
unidirectional
speed-up technique, which competes with bidirectional approaches. Moreover, we show how to exploit the advantage of unidirectional routing for fast exact queries in timetable information systems and for fast approximative queries in time-dependent scenarios. By running experiments on several inputs other than road networks, we show that our approach is very robust to the input.
Obtaining optimal
k
-cardinality trees fast
Authors: Chimani Markus , Kandyba Maria , Ljubić Ivana , Mutzel Petra
Published: April 2010

Given an undirected graph
G
= (
V
,
E
) with edge weights and a positive integer number
k
, the
k
-cardinality tree problem consists of finding a subtree
T
of
G
with exactly
k
edges and the minimum possible weight. Many algorithms have been proposed to solve this NP-hard problem, resulting in mainly heuristic and metaheuristic approaches.

In this article, we present an exact ILP-based algorithm using directed cuts. We mathematically compare the strength of our formulation to the previously known ILP formulations of this problem, and show the advantages of our approach. Afterwards, we give an extensive study on the algorithm's practical performance compared to the state-of-the-art metaheuristics.

In contrast to the widespread assumption that such a problem cannot be efficiently tackled by exact algorithms for medium and large graphs (between 200 and 5,000 nodes), our results show that our algorithm not only has the advantage of proving the optimality of the computed solution, but also often outperforms the metaheuristic approaches in terms of running time.
Shortest-path feasibility algorithms
Authors: Cherkassky Boris V. , Georgiadis Loukas , Goldberg Andrew V. , Tarjan Robert E. , Werneck Renato F.
Published: April 2010

This is an experimental study of algorithms for the shortest-path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including new algorithms) has very robust performance in practice. Our work advances the state of the art in the area.
Goal-directed shortest-path queries using precomputed cluster distances
Authors: Maue Jens , Sanders Peter , Matijevic Domagoj
Published: April 2010

We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong “sense of direction”. We evaluate our approach experimentally using large, real-world road networks.
Evaluation of online strategies for reordering buffers
Authors: Englert Matthias , Röglin Heiko , Westermann Matthias
Published: April 2010

A sequence of objects that are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces costs. A reordering buffer, which is a random access buffer with storage capacity for
k
objects, can be used to rearrange this sequence online in such a way that the total costs are reduced. This concept is useful for many applications in computer science and economics.

The strategy with the best-known competitive ratio is MAP. An upper bound of
O
(log
k
) on the competitive ratio of MAP is known and a nonconstant lower bound on the competitive ratio is not known. Based on theoretical considerations and experimental evaluations, we give strong evidence that the previously used proof techniques are not suitable to show an
o
(√log
k
) upper bound on the competitive ratio of MAP. However, we also give some evidence that in fact MAP achieves a competitive ratio of
O
(1).

Further, we evaluate the performance of several strategies on random input sequences experimentally. MAP and its variants RC and RR clearly outperform the other strategies FIFO, LRU, and MCF. In particular, MAP, RC, and RR are the only known strategies whose competitive ratios do not depend on the buffer size. Furthermore, MAP achieves the smallest competitive ratio.
Lists revisited
Authors: Frias Leonor , Petit Jordi , Roura Salvador
Published: April 2010

We present three cache-conscious implementations of STL standard compliant lists. Until now, one could either find simple doubly linked list implementations that easily cope with standard strict requirements, or theoretical approaches that do not take into account any of these requirements in their design. In contrast, we have merged both approaches, paying special attention to iterators constraints. In this article, the competitiveness of our implementations is evinced with an extensive experimental analysis. This shows, for instance, 5 to 10 times faster traversals and 3 to 5 times faster internal sort.
Engineering planar separator algorithms
Authors: Holzer Martin , Schulz Frank , Wagner Dorothea , Prasinos Grigorios , Zaroliagis Christos
Published: April 2010

We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of its nodes whose removal divides the graph into two components of similar size. These algorithms are based on planar separator theorems, which guarantee separators of size
O
(√
n
) and remaining components of size at most 2
n
/3 (where
n
denotes the number of nodes in the graph). In this article, we present a comprehensive experimental study of the classical algorithms applied to a large variety of graphs, where our main goal is to find separators that do not only satisfy upper bounds, but also possess other desirable characteristics with respect to separator size and component balance. We achieve this by investigating a number of specific alternatives for the concrete implementation and fine-tuning of certain parts of the classical algorithms. It is also shown that the choice of several parameters influences the separation quality considerably. Moreover, we propose as planar separators the usage of fundamental cycles, whose size is at most twice the diameter of the graph: For graphs of small diameter, the guaranteed bound is better than the
O
(√
n
) bounds, and it turns out that this simple strategy almost always outperforms the other algorithms, even for graphs with large diameter.
Engineering a compressed suffix tree implementation
Authors: Välimäki N. , Mäkinen V. , Gerlach W. , Dixit K.
Published: April 2010

Suffix tree is one of the most important data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length
n
from alphabet Σ = {
A
,
C
,
G
,
T
} can be stored in
n
log |Σ| = 2
n
bits, its suffix tree occupies
O
(
n
log
n
) bits. In practice, the size difference easily reaches factor 50.

We report on an implementation of the compressed suffix tree very recently proposed by Sadakane (2007). The compressed suffix tree occupies space proportional to the text size, that is,
O
(
n
log |Σ|) bits, and supports all typical suffix tree operations with at most log
n
factor slowdown. Our experiments show that, for example, on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of the normal suffix tree. At the same time, a representative algorithm is slowed down by factor 30.

Our implementation follows the original proposal in spirit, but some internal parts are tailored toward practical implementation. Our construction algorithm has time requirement
O
(
n
log
n
log |Σ|) and uses closely the same space as the final structure while constructing it: on the 10MB DNA sequence, the maximum space usage during construction is only 1.5 times the final product size. As by-products, we develop a method to create
Succinct Suffix Array
directly from Burrows-Wheeler transform and a space-efficient version of the suffixes-insertion algorithm to build balanced parentheses representation of suffix tree from LCP information.
Cache-, hash-, and space-efficient bloom filters
Authors: Putze Felix , Sanders Peter , Singler Johannes
Published: April 2010

A Bloom filter is a very compact data structure that supports approximate membership queries on a set, allowing false positives.

We propose several new variants of Bloom filters and replacements with similar functionality. All of them have a better cache-efficiency and need less hash bits than regular Bloom filters. Some use SIMD functionality, while the others provide an even better space efficiency. As a consequence, we get a more flexible trade-off between false-positive rate, space-efficiency, cache-efficiency, hash-efficiency, and computational effort. We analyze the efficiency of Bloom filters and the proposed replacements in detail, in terms of the false-positive rate, the number of expected cache-misses, and the number of required hash bits. We also describe and experimentally evaluate the performance of highly tuned implementations. For many settings, our alternatives perform better than the methods proposed so far.
Fast minimum-weight double-tree shortcutting for metric TSP
Authors: Deineko Vladimir , Tiskin Alexander
Published: April 2010

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within, at most, a factor of 2. We consider the problem of finding among these tours the one that gives the closest approximation, that is, the
minimum-weight double-tree shortcutting
. Burkard et al. gave an algorithm for this problem, running in time
O
(
n
3
+ 2

d

n
2
) and memory
O
(2

d

n
2
), where
d
is the maximum node degree in the rooted minimum spanning tree. We give an improved algorithm for the case of small
d
(including planar Euclidean TSP, where
d
≤ 4), running in time
O
(4

d

n
2
) and memory
O
(4

d

n
). This improvement allows one to solve the problem on much larger instances than previously attempted. Our computational experiments suggest that in terms of the time-quality trade-off, the minimum-weight double-tree shortcutting method provides one of the best existing tour-constructing heuristics.
Local search starting from an LP solution
Authors: Avdil Alaubek , Weihe Karsten
Published: April 2010

We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is related to the underlying problem. We consider three optimization problems: the directed MAX-CUT problem with a source and a sink and two variations of the MAX-
k
-SAT problem with
k
= 2 and
k
= 3. To compare our technique, we run local search repeatedly with random start solutions.

Our technique produces, consistently, final solutions whose objective values are not too far from the best solutions from repeated random starts. The surprising degree of stability and uniformity of this result throughout all of our experiments on various classes of instances strongly suggests that we have consistently achieved nearly optimal solutions. On the other hand, the runtime of our technique is rather small, so the technique is very efficient and probably quite accurate.
Computation in multicriteria matroid optimization
Authors: Loera Jesús A. De , Haws David C. , Lee Jon , O'Hair Allison
Published: April 2010

Motivated by recent work on algorithmic theory for nonlinear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solution of large instances of some of these difficult problems. Our methods primarily use the local adjacency structure inherent in matroid polytopes to pivot to feasible solutions, which may or may not be optimal. We also present a modified breadth-first-search heuristic that uses adjacency to enumerate a subset of feasible solutions. We present other heuristics and provide computational evidence supporting our techniques. We implemented all of our algorithms in the software package MOCHA.
Integrated safety analysis of software-controlled critical systems
Authors: Medikonda Ben Swarup , Ramaiah P. Seetha
Published: April 2010

Software for safety-critical systems must deal with the hazards identified by safety analysis in order to make the system safe, risk-free and fail-safe. Certain faults in critical systems can result in catastrophic consequences such as death, injury or environmental harm. The focus of this paper is an integrated approach to software safety analysis based on a combination of two existing fault removal techniques, and implementation of software safety in developing a small prototype safety-critical system. A comprehensive software safety analysis involving a combination of Failure Modes and Effects Analysis (FMEA) and Fault Tree Analysis (FTA) techniques is conducted on the software functions of the critical system to identify potentially hazardous software faults. A prototype safety-critical system - Railroad Crossing Control System (RCCS), incorporating a microcontroller and software to operate the train on a track circuit is described. We also briefly compare safety-specific and non-safety specific techniques at developing RCCS.
Comparing integer data structures for 32- and 64-bit keys
Authors: Nash Nicholas , Gregg David
Published: April 2010

In this article, we experimentally compare a number of data structures operating over keys that are 32- and 64-bit integers. We examine traditional comparison-based search trees as well as data structures that take advantage of the fact that the keys are integers such as van Emde Boas trees and various trie-based data structures. We propose a variant of a burst trie that performs better in time than all the alternative data structures. In addition, even for small sets of keys, this burst trie variant occupies less space than comparison-based data structures such as red-black trees and
B
-trees. Burst tries have previously been shown to provide a very efficient base for implementing cache efficient string sorting algorithms. We find that with suitable engineering, they also perform excellently as a dynamic ordered data structure operating over integer keys. We provide experimental results when the data structures operate over uniform random data. We also present experimental results for other types of data, including datasets arising from
Valgrind
, a widely used suite of tools for the dynamic binary instrumentation of programs.
High-performance operating system controlled online memory compression
Authors: Yang Lei , Dick Robert P. , Lekatsas Haris , Chakradhar Srimat
Published: April 2010

Online memory compression is a technology that increases the amount of memory available to applications by dynamically compressing and decompressing their working datasets on demand. It has proven extremely useful in embedded systems with tight physical RAM constraints. The technology can be used to increase functionality, reduce size, and reduce cost, without modifying applications or hardware. This article presents a new software-based online memory compression algorithm for embedded systems. In comparison with the best algorithms used in online memory compression, our new algorithm has a competitive compression ratio but is twice as fast. In addition, we describe several practical problems encountered in developing an online memory compression infrastructure and present solutions. We present a method of adaptively managing the uncompressed and compressed memory regions during application execution. This memory management scheme adapts to the predicted memory requirements of applications. It permits efficient compression for a wide range of applications. We have evaluated our techniques on a portable embedded device and have found that the memory available to applications can be increased by 2.5× with negligible performance and power consumption penalties, and with no changes to hardware or applications. Our techniques allow existing applications to execute with less physical memory. They also allow applications with larger working datasets to execute on unchanged embedded system hardware, thereby increasing functionality.
Feasibility of semiring-based timing constraints
Authors: Yu Yue , Ren Shangping , Frieder Ophir
Published: April 2010

Real-time and embedded applications often involve different types of timing constraints, such as precedence constraints and real-time constraints. As real-time and embedded applications further advance, new timing constraint types are emerging as well. Recent research on interval-based timing constraints is an example. Thus, it is important to have a uniformed timing constraint representation so that a generalized approach can be developed to analyze the variant constraint types.

A semiring-based timing constraint model is introduced to generalize the representations of different constraint types. Under this model, we develop an algorithm to check the satisfaction feasibility for a given set of semiring-based timing constraints. This algorithm provides better performance in the average case as compared to applying the Bellman-Ford algorithm directly on the constraint set.

In addition, for a set of feasible semiring-based timing constraints, event occurrence points that satisfy the constraint set form a (hyperdimension) feasible region. For the given two sets of timing constraints, we develop a necessary and sufficient condition to testify whether the two constraint sets' feasible regions have an inclusion relation. If one feasible region is included in the other, we know that the real-time event occurrences that satisfy the included constraint set will necessarily satisfy the including set.
A polynomial algorithm for partitioning problems
Authors: Tahaee Seyed-Abdoreza , Jahangir Amir Hossein
Published: April 2010

This article takes a theoretical approach to focus on the algorithmic properties of hardware/software partitioning. It proposes a method with polynomial complexity to find the global optimum of an NP-hard model partitioning problem for 75% of occurrences under some practical conditions. The global optimum is approached with a lower bound distance for the remaining 25%. Furthermore, this approach ensures finding the 2-approximate of the global optimum partition in 97% of instances where technical assumptions exist. The strategy is based on intelligently changing the parameters of the polynomial model of the partitioning problem to force it to produce (or approach) the exact solution to the NP-hard model.
An optimal warning-zone-length assignment algorithm for real-time and multiple-QoS on-chip bus arbitration
Authors: Peng Huan-Kai , Lin Youn-Long
Published: April 2010

In an advanced System-on-Chip (SoC) for real-time applications, the arbiter of its on-chip communication subsystem needs to support multiple QoS criteria while providing a hard real-time guarantee. To fulfill both objectives, the arbitration algorithm must dynamically switch between NonReal-Time (NRT) and Real-Time (RT) modes such that use of the RT mode is minimized to best accommodate the overall QoS criteria. In this article, we define a model for this problem, and propose optimal solutions to its associated problems with static and dynamic warning-zone-length assignment. Compared with previous works, the proposed approach enables a bus arbiter to use much less RT mode in providing a Real-Time (RT) guarantee and, therefore, gives the arbiter more opportunity to employ non-RT modes to achieve better overall QoS. Experimental results show that the proposed approach reduces RT mode usage by as much as 37.1%. Moreover, that reduction in RT mode usage helps cut the execution time by 27.0% when applying our approach to an industrial DRAM controller. Another case study on an AMBA-compliant ultra-high-resolution H.264 decoder IP shows that the proposed approach reduces RT mode usage by 26.4%, which leads to an average reduction of 10.4% in decoding time. Finally, when implementing a 16 master arbiter, it costs only 6.9K and 9.5K gates of overhead using the proposed static and dynamic approach, respectively. Therefore, the proposed approach is suitable for real-time SoC applications.
Model checking of software for microcontrollers
Authors: Schlich Bastian
Published: April 2010

The interest of industries in model checking software for microcontrollers is increasing. However, there are currently no appropriate tools that can be applied by embedded systems developers for the direct verification of software for microcontrollers without the need for manual modeling. This article describes a new approach to model checking software for microcontrollers, which verifies the assembly code of the software. The state space is built using a tailored simulator, which abstracts from time, handles nondeterminism, and creates an overapproximation of the behavior shown by the real microcontroller. Within this simulator, we apply abstraction techniques to tackle the state-explosion problem. In our approach, we combine different formal methods, namely, model checking, static analysis, and abstract interpretation. We also combine explicit and symbolic model checking techniques. This article presents a case study using several programs to demonstrate the efficiency of the applied abstraction techniques and to show the applicability of this approach.
Experiments on the preference-based organization interface in recommender systems
Authors: Chen Li , Pu Pearl
Published: April 2010

As e-commerce has evolved into its second generation, where the available products are becoming more complex and their abundance is almost
unlimited
, the task of locating a desired choice has become too difficult for the average user. Therefore, more effort has been made in recent years to develop recommender systems that recommend products or services to users so as to assist in their decision-making process. In this article, we describe crucial experimental results about a novel recommender technology, called the
preference-based organization
(Pref-ORG), which generates critique suggestions in addition to recommendations according to users' preferences. The critique is a form of feedback (“I would like something cheaper than this one”) that users can provide to the currently displayed product, with which the system may better predict what the user truly wants. We compare the
preference-based organization
technique with related approaches, including the ones that also produce critique candidates, but without the consideration of user preferences. A simulation setup is first presented, that identified Pref-ORG's significantly higher algorithm accuracy in predicting critiques and choices that users should intend to make, followed by a real-user evaluation which practically verified its significant impact on saving users' decision effort.
Perfect matchings via uniform sampling in regular bipartite graphs
Authors: Goel Ashish , Kapralov Michael , Khanna Sanjeev
Published: April 2010

In this article we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first nontrivial algorithm, with running time
O
(
mn
), dates back to König's work in 1916 (here
m
=
nd
is the number of edges in the graph, 2
n
is the number of vertices, and
d
is the degree of each node). The currently most efficient algorithm takes time
O(m)
, and is due to Cole et al. [2001]. We improve this running time to
O
(min{
m
,
n
2.5
ln
n
/
d
}); this minimum can never be larger than
O
(
n
1.75
√ln
n
). We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a
d
-regular bipartite graph independently with a probability
p
=
O
(
n
ln
n
/
d
2
) then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to nonexistence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem [1994a, 1994b] for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the
O
(
m
√
n
) algorithm (due to Hopcroft and Karp [1973]) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to polylogarithmic factors (in fact, up to ln
2
n
).
A 4
k
2
kernel for feedback vertex set
Authors: Thomassé Stéphan
Published: April 2010

We prove that given an undirected graph
G
on
n
vertices and an integer
k
, one can compute, in polynomial time in
n
, a graph
G′
with at most 4
k
2
vertices and an integer
k′
such that
G
has a feedback vertex set of size at most
k
iff
G′
has a feedback vertex set of size at most
k′
. This result improves a previous
O
(
k
11
) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.
Truthful unsplittable flow for large capacity networks
Authors: Azar Yossi , Gamzu Iftah , Gutner Shai
Published: April 2010

The
unsplittable flow problem
is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated with source and target vertices, a demand, and a value. The objective is to route a maximum value subset of requests subject to the edge capacities. It is a well known fact that as the capacities of the edges are larger with respect to the maximal demand among the requests, the problem can be approximated better. In particular, it is known that for sufficiently large capacities, the integrality gap of the corresponding integer linear program becomes 1 + ϵ, which can be matched by an algorithm that utilizes the randomized rounding technique.

In this article, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, which attains an approximation ratio of
e
/
e
-1, up to a disparity of ϵ away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a monotone PTAS, if that exists, one would have to exert different techniques. We also consider the large capacities
single-minded multi-unit combinatorial auction problem
. This problem is closely related to the unsplittable flow problem since one can formulate it as a special case of the integer linear program of the unsplittable flow problem. Accordingly, we obtain a comparable performance guarantee by refining the algorithm suggested for the unsplittable flow problem.
Facility location with hierarchical facility costs
Authors: Svitkina Zoya , Tardos ÉVA
Published: April 2010

We introduce a facility location problem with submodular facility cost functions, and give an
O
(log
n
) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + ϵ)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.
The $100 laptop
Authors: Harris Danielle
Published: April 2010

One Laptop per Child (OLPC) attempts to bridge the "digital divide" between the rich and the poor, especially in third-world countries. In order to accomplish this, OLPC must introduce twenty-first century technology to the poverty-stricken, which can lead to more efficient means of education. Nicholas Negroponte, founder of OLPC, explains that in his opinion, "whatever big problem you can imagine, from world peace to the environment to hunger to poverty, the solution always includes education" (Pontin). The first step to improving education in poverty-stricken countries, according to OLPC, is providing children with an inexpensive yet functional laptop, informally known as the $100 laptop.
Genesis of multipeaked waves of the esophagus: repetitive contractions or motion artifact?
Authors: Sampath Neha J. , Bhargava Valmik , Mittal Ravinder K.
Published: April 2010

Multipeaked waves (MPW) in the distal esophagus occur frequently in patients with esophageal spastic motor disorders and diabetes mellitus and are thought to represent repetitive esophageal contractions. We aimed to investigate whether the relative motion between a stationary pressure sensor and contracted peristaltic esophageal segment that moves with respiration leads to the formation of MPW. We mathematically modeled the effect of relative movement between a moving pressure segment and a fixed pressure sensor on the pressure waveform morphology. We conducted retrospective analysis of 100 swallow-induced esophageal contractions in 10 patients, who demonstrated >30% MPW on high-resolution manometry (HRM) during standardized swallows. Finally, using HRM, we determined the effects of suspended breathing and hyperventilation on the waveform morphology in 10 patients prospectively. Modeling revealed that relative movement between a stationary pressure sensor and a moving contracted segment, contraction duration, contraction amplitude, respiratory frequency, and depth of respiration affects the waveform morphology. Retrospective analysis demonstrated a close temporal association with the onset of second and subsequent contractions in MPW with respiratory phase reversals. Numbers of peaks in MPW and respiratory phase reversals were closely related to the duration of contraction. In the prospective study, suspended breathing and hyperventilation resulted in a significant decrease and increase in the MPW frequency as well as the number of peaks within MPW respectively. We conclude that MPW observed during clinical motility studies are not indicative of repetitive esophageal contraction; rather they represent respiration-related movement of the contracted esophageal segment in relation to the stationary pressure sensor.
Cellular effects of gastric electrical stimulation on antral smooth muscle cells in rats
Authors: Li Shiying , Chen Jiande D. Z.
Published: April 2010

The cellular effects of gastric electrical stimulation (GES), which has recently been introduced as a potential therapy for the treatment of gastroparesis and obesity, were investigated in rat antrum smooth muscle cells (SMCs). Effects on cell membrane potentials of single electrical current pulses (pulse width from 0.1 ms to 200 ms) and 2-s pulse train stimuli with different pulse widths (0.1–4 ms), different frequencies (20–200 Hz), and different intensities were studied: 1) the stimulus amplitude had an exponential relationship to the pulse width from 2 ms to 200 ms, along with a rapidly rising strength-duration curve at pulse widths less than 5 ms, and a relatively flat curve at pulse widths greater than 50 ms; 2) when the pulse frequency was at 80 Hz or above, pulse train electrical stimulation, with a pulse width of 2 ms or above but not ≤1 ms, was able to depolarize cell membrane potentials to above −30 mV and/or generate action potentials. Electrical stimulation with a single long pulse and a width of 50 ms or greater is effective in depolarizing cell membrane potentials of SMCs with low amplitude. Pulse train electrical stimulation with a pulse width of ≤1 ms fails to generate action potentials in SMCs, whereas pulse train electrical stimulation with a pulse width of 2–4 ms and a sufficiently high pulse frequency is able to generate action potentials. These cellular findings may be useful in optimizing stimulation parameters of GES.
Adaptive trends in respiratory control: a comparative perspective
Authors: Milsom William K.
Published: April 2010

In 1941, August Krogh published a monograph entitled The Comparative Physiology of Respiratory Mechanisms (Philadelphia, PA: University of Pennsylvania Press, 1941). Since that time comparative studies have continued to contribute significantly to our understanding of the fundamentals of respiratory physiology and the adaptive trends in these processes that support a broad range of metabolic performance under demanding environmental conditions. This review specifically focuses on recent advances in our understanding of adaptive trends in respiratory control. Respiratory rhythm generators most likely arose from, and must remain integrated with, rhythm generators for chewing, suckling, and swallowing. Within the central nervous system there are multiple “segmental” rhythm generators, and through evolution there is a caudal shift in the predominant respiratory rhythm-generating site. All sites, however, may still be capable of producing or modulating respiratory rhythm under appropriate conditions. Expression of the respiratory rhythm is conditional on (tonic) input. Once the rhythm is expressed, it is often episodic as the basic medullary rhythm is turned on/off subject to a hierarchy of controls. Breathing patterns reflect differences in pulmonary mechanics resulting from differences in body wall and lung architecture and are modulated in different species by various combinations of upper and lower airway mechanoreceptors and arterial chemoreceptors to protect airways, reduce dead space ventilation, enhance gas exchange efficiency, and reduce the cost of breathing.
Locomotor activity and gait in aged mice deficient for type IX collagen
Authors: Costello Kerry E. , Guilak Farshid , Setton Lori A. , Griffin Timothy M.
Published: April 2010

Osteoarthritis (OA) is a risk factor for physical inactivity and impaired mobility, but it is not well understood how these locomotor behaviors are affected by the age of onset of OA and disease severity. Male mice homozygous for a Col9a1 gene inactivation ( Col9a1−/−) develop early onset knee OA, increased tactile pain sensitivity, and gait alterations by 9 mo of age. We hypothesized that aged Col9a1−/− mice would reduce joint pain by adopting locomotor behaviors that reduce both the magnitude and daily frequency of joint loading. We tested this hypothesis by evaluating gait and spontaneous locomotor activity in 15- to 17-mo-old male Col9a1−/− ( n = 5) and Col9a1+/+(WT) ( n = 5) mice using well-controlled measures of voluntary activity in overground and running wheel conditions, as well as studies of gait in a velocity-controlled treadmill. We found no difference due to genotype in freely chosen locomotor velocity, stride frequency, hindfoot duty factor, dark phase activity time, or dark-phase travel distance during overground, running wheel, or speed-matched treadmill locomotion. Interpretation of these findings is potentially confounded by the observation that WT mice have greater knee OA than Col9a1−/− mice in the lateral tibial plateau by 17 mo of age. When accounting for individual differences in knee OA, functional locomotor impairments in aged Col9a1−/− and WT mice are manifested as reductions in total locomotor activity levels (e.g., both distance traveled and time active), particularly for wheel running. These results support the concept that current disease status, rather than age of disease onset, is the primary determinant of impaired locomotor activity with aging.
An integrative model of motor unit activity during sustained submaximal contractions
Authors: Dideriksen Jakob L. , Farina Dario , Baekgaard Martin , Enoka Roger M.
Published: April 2010

The purpose of the study was to expand a model of motor unit recruitment and rate coding ( 30 ) to simulate the adjustments that occur during a fatiguing contraction. The major new components of the model were the introduction of time-varying parameters for motor unit twitch force, recruitment, discharge rate, and discharge variability, and a control algorithm that estimates the net excitation needed by the motoneuron pool to maintain a prescribed target force. The fatigue-induced changes in motor unit activity in the expanded model are a function of changes in the metabolite concentrations that were computed with a compartment model of the intra- and extracellular spaces. The model was validated by comparing the simulation results with data available from the literature and experimentally recorded in the present study during isometric contractions of the first dorsal interosseus muscle. The output of the model was able to replicate a number of experimental findings, including the time to task failure for a range of target forces, the changes in motor unit discharge rates, the skewness and kurtosis of the interspike interval distributions, discharge variability, and the discharge characteristics of newly recruited motor units. The model output provides an integrative perspective of the adjustments during fatiguing contractions that are difficult to measure experimentally.
Fatigue and Motor Redundancy: Adaptive Increase in Finger Force Variance in Multi-Finger Tasks
Authors: Singh Tarkeshwar , SKM Varadhan , Zatsiorsky Vladimir M. , Latash Mark L.
Published: April 2010

We studied the effects of fatigue of the index finger on indices of force variability in discrete and rhythmic accurate force production tasks performed by the index finger and by all four fingers pressing in parallel. An increase in the variance of the force produced by the fatigued index finger was expected. We hypothesized that the other fingers would also show increased variance of their forces, which would be accompanied by co-variation among the finger forces resulting in relatively preserved accuracy of performance. The subjects performed isometric tasks including maximal voluntary contraction (MVC) and accurate force production before and after a 1-min MVC fatiguing exercise by the index finger. During fatigue, there was a significant increase in the root mean square index of force variability during accurate force production by the index finger. In the four-finger tasks, the variance of the individual finger force increased for all four fingers, while the total force variance showed only a modest change. We quantified two components of variance in the space of hypothetical commands to fingers, finger modes. There was a large increase in the variance component that did not affect total force and a much smaller increase in the component that did. The results suggest an adaptive increase in force variance by nonfatigued elements as a strategy to attenuate effects of fatigue on accuracy of multi-element performance. These effects were unlikely to originate at the level of synchronization of motor units across muscle compartments but rather involved higher control levels.
Hebbian Analysis of the Transformation of Medial Entorhinal Grid-Cell Inputs to Hippocampal Place Fields
Authors: Savelli Francesco , Knierim James J.
Published: April 2010

The discovery of grid cells in the medial entorhinal cortex (MEC) permits the characterization of hippocampal computation in much greater detail than previously possible. The present study addresses how an integrate-and-fire unit driven by grid-cell spike trains may transform the multipeaked, spatial firing pattern of grid cells into the single-peaked activity that is typical of hippocampal place cells. Previous studies have shown that in the absence of network interactions, this transformation can succeed only if the place cell receives inputs from grids with overlapping vertices at the location of the place cell's firing field. In our simulations, the selection of these inputs was accomplished by fast Hebbian plasticity alone. The resulting nonlinear process was acutely sensitive to small input variations. Simulations differing only in the exact spike timing of grid cells produced different field locations for the same place cells. Place fields became concentrated in areas that correlated with the initial trajectory of the animal; the introduction of feedback inhibitory cells reduced this bias. These results suggest distinct roles for plasticity of the perforant path synapses and for competition via feedback inhibition in the formation of place fields in a novel environment. Furthermore, they imply that variability in MEC spiking patterns or in the rat's trajectory is sufficient for generating a distinct population code in a novel environment and suggest that recalling this code in a familiar environment involves additional inputs and/or a different mode of operation of the network.
Role of the Rostral Superior Colliculus in Gaze Anchoring During Reach Movements
Authors: Reyes-Puerta Vicente , Philipp Roland , Lindner Werner , Hoffmann Klaus-Peter
Published: April 2010

When reaching for an object, primates usually look at their target before touching it with the hand. This gaze movement prior to the arm movement allows target fixation, which is usually prolonged until the target is reached. In this manner, a stable image of the object is provided on the fovea during the reach, which is crucial for guiding the final part of the hand trajectory by visual feedback. Here we investigated a neural substrate possibly responsible for this behavior. In particular we tested the influence of reaching movements on neurons recorded at the rostral pole of the superior colliculus (rSC), an area classically related to fixation. Most rSC neurons showed a significant increase in their activity during reaching. Moreover, this increase was particularly high when the reaching movements were preceded by corresponding saccades to the targets to be reached, probably revealing a stronger coupling of the oculo-manual neural system during such a natural task. However, none of the parameters tested—including movement kinematics and target location—was found to be closely related to the observed increase in neural activity. Thus the increase in activity during reaching was found to be rather nonspecific except for its dependence on whether the reach was produced in isolation or in combination with a gaze movement. These results identify the rSC as a neural substrate sufficient for gaze anchoring during natural reaching movements, placing its activity at the core of the neural system dedicated to eye-hand coordination.
Malaria, Intestinal Helminths and Other Risk Factors for Stillbirth in Ghana
Authors: Yatich Nelly J. , Funkhouser Ellen , Ehiri John E. , Agbenyega Tsiri , Stiles Jonathan K. , Rayner Julian C. , Turpin Archer , Ellis William O. , Jiang Yi , Williams Jonathan H. , Afriyie-Gwayu Evans , Phillips Timothy , Jolly Pauline E.
Published: April 2010

Objective. The objective of the study was to assess Plasmodium/intestinal helminth infection in pregnancy and other risk factors for stillbirth in Ghana.Methods. A cross-sectional study of women presenting for delivery in two hospitals was conducted during November-December 2006. Data collected included sociodemographic information, medical and obstetric histories, and anthropometric measures. Laboratory investigations for the presence ofPlasmodium falciparumand intestinal helminths, and tests for hemoglobin levels were also performed.Results. The stillbirth rate was relatively high in this population (5%). Most of the stillbirths were fresh and 24% were macerated. When compared to women with no malaria, women with malaria had increased risk of stillbirth (OR=1.9, 95% CI=1.2–9.3). Other factors associated with stillbirth were severe anemia, low serum folate concentration, past induced abortion, and history of stillbirth.Conclusion. The fact that most of the stillbirths were fresh suggests that higher quality intrapartum care could reduce stillbirth rates.
Geometric Sensitivity of a Pinhole Collimator
Authors: Jacobowitz Howard , Metzler Scott D.
Published: April 2010

Geometric sensitivity for single photon emission computerized tomography
(SPECT) is given by a double integral over the detection plane. It
would be useful to be able to explicitly evaluate this quantity. This paper
shows that the inner integral can be evaluated in the situation where
there is no gamma ray penetration of the material surrounding the pinhole
aperture. This is done by converting the integral to an integral in
the complex plane and using Cauchy′s theorem to replace it by one which
can be evaluated in terms of elliptic functions.